1 /* 2     最短路：Floyd算法模板题 3 */ 4 #include 
     
       5 #include 
      
        6 #include 
       
         7 #include 
        
          8 #include 
         
           9 #include 
          
           10 #include 
           
            11 using namespace std;12 13 const int MAXN = 200 + 10;14 const int INF = 0x3f3f3f3f;15 double d[MAXN][MAXN];16 int used[MAXN];17 struct NODE18 {19 int x, y;20 }node[MAXN];21 22 double dis(int j, int i)23 {24 return sqrt ((node[j].x - node[i].x) * (node[j].x - node[i].x) + (node[j].y - node[i].y) * (node[j].y - node[i].y));25 }26 27 void Floyd_Warshall(int n)28 {29 for (int k=1; k<=n; ++k)30 {31 for (int i=1; i<=n-1; ++i)32 {33 for (int j=i+1; j<=n; ++j)34 {35 if (d[i][k] < d[i][j] && d[k][j] < d[i][j])36 {37 if (d[i][k] < d[k][j])38 d[i][j] = d[j][i] = d[k][j];39 else40 d[i][j] = d[j][i] = d[i][k];41 }42 }43 }44 }45 46 printf ("Frog Distance = %.3f\n", d[1][2]);47 }48 49 int main(void) //POJ 2253 Frogger50 {51 //freopen ("D.in", "r", stdin);52 53 int n;54 int cnt = 0;55 int first = 1;56 while (~scanf ("%d", &n) && n)57 {58 for (int i=1; i<=n; ++i)59 {60 scanf ("%d%d", &node[i].x, &node[i].y);61 }62 for (int i=1; i<=n-1; ++i)63 {64 for (int j=i+1; j<=n; ++j)65 {66 d[i][j] = d[j][i] = dis (i, j);67 }68 }69 70 printf ("Scenario #%d\n", ++cnt);71 Floyd_Warshall (n);72 puts ("");73 }74 75 return 0;76 }77 78 79 80 81 /*82 Scenario #183 Frog Distance = 5.00084 85 Scenario #286 Frog Distance = 1.41487 */