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也可以变种呀~附0msdij代码#include<iostream> #include<stdio.h> #include<string.h> #include<math.h> using namespace std; #define inf 0x7fffffff int x[210],y[210],n,mark[210]; double map[210][210],v[210]; double getit(int i,int j) { int d; double f; d=(y[i]-y[j])*(y[i]-y[j])+(x[i]-x[j])*(x[i]-x[j]); f=sqrt(d); return f; } double max(double a,double b) { if(a>=b) return a; else return b; } double dijkstra() { memset(mark,0,sizeof(mark)); int i,j,k; double t,ans=0; for(i=0;i<n;i++) { v[i]=map[0][i]; } v[i]=0; mark[0]=1; for(i=1;i<n;i++) { t=inf; //t=v[i]; for(j=0;j<n;j++) { if(!mark[j]&&v[j]<t) { t=v[j]; k=j; } } mark[k]=1; for(j=0;j<n;j++) { double temp=max(map[k][j],v[k]); if(temp<v[j]) v[j]=temp; } } ans=v[1]; return ans; } int main() { int i,j,k,test=0; double weight,ans; while(scanf("%d",&n)==1) { test++; memset(map,0,sizeof(map)); if(n==0) break; for(i=0;i<n;i++) { for(j=0;j<n;j++) map[i][j]=inf; map[i][i]=0; } for(i=0;i<n;i++) { scanf("%d%d",&x[i],&y[i]); for(j=0;j<i;j++) { weight=getit(i,j); map[i][j]=weight; map[j][i]=weight; } } ans=dijkstra(); printf("Scenario #%d\n",test); printf("Frog Distance = %.3f\n\n",ans); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator