| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
这个题不就是dij的变形吗?高人帮我看下代码错在哪里?#include <iostream>
#include <queue>
#include <vector>
#include <iomanip>
#include <cmath>
using namespace std;
int N;
struct NODE{
int x;int y;
}node[201];
double longest[201];
bool vis[201];
double d[201][201];
inline double dis(int a,int b)
{
return sqrt(1.0*(node[a].x-node[b].x)*(node[a].x-node[b].x)+
1.0*(node[a].y-node[b].y)*(node[a].y-node[b].y));
}
struct cmp
{
bool operator () (const int &a,const int &b)
{
return longest[a]>longest[b];
}
};
double djs()
{
priority_queue<int,vector<int>,cmp> pq;
longest[1] = 0.0;
pq.push(1);
while(!pq.empty())
{
int x = pq.top();
pq.pop();
// cout << "vis" <<x << endl;
vis[x] = 1;
if(x==2) return longest[2];
for(int i = 1; i <= N; i++)
{
if(vis[i]) continue;
if(longest[i]>(longest[x]>d[i][x]?longest[x]:d[i][x]))
{
longest[i] = longest[x]>d[i][x]?longest[x]:d[i][x];
pq.push(i);
}
}
}
return -1;
}
int main()
{
int t=1;
while(scanf("%d",&N)&&N!=0)
{
memset(node,0,sizeof(node));
memset(d,0,sizeof(d));
memset(vis,0,sizeof(vis));
for(int i = 1; i <= N; i++)
longest[i] = 10000000.0;
for(int i = 1; i <= N; i++)
{
scanf("%d %d",&node[i].x,&node[i].y);
for(int j = 1; j <= i; j++){
d[i][j] = d[j][i] = dis(i,j);
}
}
cout << "Scenario #" << t <<endl
<< "Frog Distance = " << setiosflags(ios::fixed) << setprecision(3) << djs() << endl << endl;
t++;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator