POJ2253 Frogger

　　求最长路中的最短路……略显绕嘴最长路定义为该条路上青蛙调的最远的那一步。应该算是水题，感觉思路比较新颖，主要是权值的定义。

　　两种算法很显然后一种从效率上明显优于前一种

　　Floyd

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <algorithm>
 7 #include <queue>
 8 
 9 using namespace std;
10 
11 float path[210][210];
12 
13 float Max(float a,float b)
14 {
15     return a > b ? a : b;
16 }
17 
18 int main()
19 {
20     int icase = 0;
21 
22     int n,i,j,k;
23     int dx[210],dy[210];
24 
25     while(cin>>n && n)
26     {
27 
28         for(i = 0;i < n; i++)
29             cin>>dx[i]>>dy[i];
30 
31         for(i = 0;i < n; i++)
32             for(j = 0;j <  n; j++)
33             {
34                 path[i][j] = sqrt((dx[i]-dx[j])*(dx[i]-dx[j]) + (dy[i]-dy[j])*(dy[i]-dy[j]));
35             }
36 
37         for(i = 0;i < n; i++)
38             for(j = 0;j < n; j++)
39                 for(k = 0;k < n; k++)
40                 {
41                     if(i != j && j != k && i != k && path[j][k] > Max(path[j][i],path[i][k]))
42                         path[j][k] = Max(path[j][i],path[i][k]);
43                 }
44 
45         printf("Scenario #%d
",++icase);
46         printf("Frog Distance = %.3f

",path[0][1]);
47 
48 
49     }
50     return 0;
51 }

Bellman_ford

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <algorithm>
 7 #include <queue>
 8 
 9 using namespace std;
10 
11 float path[210][210];
12 
13 float Max(float a,float b)
14 {
15     return a > b ? a : b;
16 }
17 
18 struct N
19 {
20     float dis;
21     int u,v;
22 }edge[101010];
23 
24 float dis[1000];
25 
26 void sp(int n,int m)
27 {
28     int i,j;
29     bool mark;
30 
31     dis[0] = 0;
32 
33     for(i = 0;i < n; i++)
34     {
35         for(mark = true,j = 0;j < m; j++)
36         {
37             if(dis[edge[j].v] > Max(edge[j].dis,dis[edge[j].u]))
38             {
39                 dis[edge[j].v] =  Max(edge[j].dis,dis[edge[j].u]);
40                 mark = false;
41             }
42         }
43         if(mark)
44             return ;
45     }
46 }
47 
48 int main()
49 {
50     int icase = 0;
51 
52     int n,i,j;
53     int dx[210],dy[210];
54     int top;
55     float len;
56 
57     while(cin>>n && n)
58     {
59 
60         for(i = 0;i < n; i++)
61             cin>>dx[i]>>dy[i];
62 
63         for(top = 0,i = 0;i < n; i++)
64             for(j = i+1;j <  n; j++)
65             {
66 
67                 len = sqrt((dx[i]-dx[j])*(dx[i]-dx[j]) + (dy[i]-dy[j])*(dy[i]-dy[j]));
68                 if(i == 0)
69                     dis[j] = len;
70                 edge[top].dis = len;
71                 edge[top].u = i;
72                 edge[top].v = j;
73                 edge[++top].dis = len;
74                 edge[top].u = j;
75                 edge[top++].v = i;
76             }
77         sp(n,top);
78         printf("Scenario #%d
",++icase);
79         printf("Frog Distance = %.3f

",dis[1]);
80 
81 
82     }
83     return 0;
84 }

相关推荐