poj 2253 Frogger
#include <iostream> #include <stdio.h> #include <queue> #include <math.h> #define N 202 using namespace std; double a[N][N]; int n; double d[N]; bool f[N]; struct point{ int x, y; }p[202]; double find_edge(int u, int v){ float dx = p[u].x - p[v].x; float dy = p[u].y - p[v].y; return sqrt(dx * dx + dy * dy); } void dij(){ int i,j; memset(f,0,sizeof(f)); for(i=1;i<=n;i++){ d[i]=a[1][i]; } f[1]=1; d[1]=0; for(i=1;i<n;i++){ double min=100*100*127; int u; for(j=1;j<=n;j++){ if(!f[j]&&d[j]<min){ min=d[j]; u=j; } } if(u==n)return; f[u]=1; for(j=1;j<=n;j++){ if(!f[j]){ if(a[u][j]<=min) d[j]=min; if(a[u][j]>min){ if(d[j]>a[u][j]) d[j]=a[u][j]; } } } } } int main(){ int t=1; while(cin>>n&&n!=0){ memset(a,0,sizeof(a)); int i,j; cin>>p[1].x>>p[1].y; cin>>p[n].x>>p[n].y; if(i>2) for(i=2;i<=n-1;i++){ cin>>p[i].x>>p[i].y; } for(i=1;i<=n;i++){ for(j=i+1;j<=n;j++){ a[i][j]= find_edge(i, j); a[j][i]=a[i][j]; } } dij(); printf("Scenario #"); printf("%d\nFrog Distance = %.3lf\n\n",t++,d[n]); } return 0; }