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 |
Dijkstra 改一下松弛条件就好了。// // main.cpp // poj 2253 // // Created by on 16/6/4. // Copyright © 2016年 . All rights reserved. // 注意sqrt里面不支持int类型,改成double以防RE #include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std; int n,x[210],y[210]; double g[210][210]; double dij(int u,int v) { int i,j,k; bool b[210]; double h,zmin,dist[210]; memset(b,true,sizeof(b)); for (i = 1; i <= n; ++i) { dist[i] = g[u][i]; b[i] = true; } dist[u] = 0; b[u] = false; for (i = 1; i < n; ++i) { zmin = 99999999; for (j = 1; j <= n; ++j) if (b[j]&&dist[j]<zmin) { zmin = dist[j]; k = j; } b[k] = false; for (j = 1; j <= n; ++j) { h = max(dist[k],g[k][j]); dist[j] = min(dist[j],h); } } return dist[2]; } int main(int argc, const char * argv[]) { int i,j,k,p; p = 0; while (cin >> n) { p++; memset(g,0,sizeof(g)); if (n == 0) break; for (i = 1; i <= n; ++i) { scanf("%d%d",&x[i],&y[i]); } for (i = 1; i <= n; ++i) { for (j = 1; j <= n; ++j) if (i==j) g[i][i] = 0; else g[i][j] = sqrt(1.0*(x[i]-x[j])*(x[i]-x[j])+1.0*(y[i]-y[j])*(y[i]-y[j])); } printf("Scenario #%d\n",p); printf("Frog Distance = %.3f\n",dij(1,2)); puts(""); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator