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 |
这道题目flody就可以过了不用写dijstra和spfa算法附代码给大家!!!如有雷同我就去死!#include <stdio.h> #include <string.h> #include <math.h> #define len 210 #define MAX 100000000 double max(double a,double b) { if(a>b) return a; else return b; } double min(double a,double b) { if(a>b) return b; else return a; } double road[len][len]; typedef struct node { double x; double y; }Node; Node point[len]; int n,times; void flody() { int i,j,k; for(k=1;k<=n;k++) { for(i=1;i<=n;i++) { for(j=1;j<=n;j++) road[i][j]=min(road[i][j],max(road[i][k],road[k][j])); } } printf("Scenario #%d\n",times++); printf("Frog Distance = %.3lf\n",road[1][2]); printf("\n"); } int main() { int i,j,k; double d; times=1; while(scanf("%d",&n)!=EOF&&n) { getchar(); for(k=1;k<=n;k++) scanf("%lf %lf",&point[k].x,&point[k].y); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) road[i][j]=MAX; road[i][i]=0; } for(i=1;i<=n;i++) { for(j=1;j<i;j++) { d=sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y)); road[i][j]=d; road[j][i]=d; } } /* for(i=1;i<=n;i++) { for(j=1;j<=n;j++) printf("%lf ",road[i][j]); printf("\n"); } */ flody(); } return 1; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator