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