Zhao70's Blog

POJ2253 Frogger

发表于 | 分类于

题目大意

POJ2253 Frogger

图中的一个点到另一个点, 每条路径都有一个最大的跳跃长度, 求所有路径的最大跳跃长度当中最小值.

涉及知识点

其实是考察最短路算法(Dijkstra, Floyd等)的变形, Dijkstra 和 Floyd 算法通常用来求最短路, 但其实只要改变边的松弛条件, 存储边的数组的含义便会发生改变, 比如PAT10031(使用Dijkstra可以求带点权图的最短路).

使用Dijkstra

思路

根据题目要求, dis数组的含义变为从一个点出发, 到其他点的最长路径中的最小值, 因此, dis的松弛条件变为 dis[v] = min(dis[v], max(dis[u], edge[u][v])), 所以说用Dijkstra的变形的时候一定要考虑不同的松弛条件, dis数组的含义是不同的

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <cmath>
#include <iomanip>
#include <cstring>
#include <cmath>
using namespace std;
double max(double a, double b){
  return a > b ? a : b;
}
double mina(double a, double b){
  return a < b ? a : b;
}
const int maxn = 210;
struct Point{
  int x, y;
}arr[maxn];
double getDis(Point a, Point b){
  return sqrt((a.x - b.x) * (a.x  - b.x) + (a.y - b.y) * (a.y - b.y));
}
double edge[maxn][maxn];
double dijkstra(int nC){
  double dis[maxn];
  for(int i = 0; i < nC; ++i){
    dis[i] = edge[0][i];
  }
  bool isVis[maxn];
  for(int i = 0; i < nC; ++i)
    isVis[i] = false;
  isVis[0] = true;
  for(int i = 0; i < nC; ++i){
    int u;
    double min = 99999;
    for(int j = 0; j < nC; j++){
      if(isVis[j])
        continue;
      if(dis[j] < min){
        min = dis[j];
        u = j;
      }
    }
    isVis[u] = true;
    for(int v = 0; v < nC; ++v){
      dis[v] = mina(dis[v], max(dis[u], edge[u][v]));
    }
  }
  return dis[1];
}
int main(){
  int t = 0;
  int nCase;
  while(cin >> nCase && nCase != 0){
    t++;
    for(int i = 0; i < nCase; i++){
      cin >> arr[i].x >> arr[i].y;
    }
    for(int i = 0; i < maxn; i++){
      for(int j = 0; j < maxn; j++)
        edge[i][j] = 0;
    }
    for(int i = 0; i < nCase; i++){
      for(int j = i + 1; j < nCase; j++){
        edge[i][j] = edge[j][i] = getDis(arr[i], arr[j]);
      }
    }
    //
    // for(int i = 0; i < nCase; i++){
    //   for(int j = 0; j < nCase; j++)
    //     cout << edge[i][j] << " ";
    //   cout << endl;
    // }
    //
    cout << "Scenario #" << t << "\nFrog Distance = " << fixed << setprecision(3) << dijkstra(nCase) << endl << endl;
  }
  return 0;
}

使用Floyd

思路

同理, 根据题目要求, Floyed中的edge数组, 代表不同两点之间最长路径的最小值. 因此, 松弛条件为 edge[i][j] = min(edge[i][j], max(edge[i][k], edge[k][j]));

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include <cmath>
#include <cstdio>
#include <iomanip>
using namespace std;
struct Point{
  int x, y;
};
Point arr[210];
double getDis(Point a, Point b){
  return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double edge[210][210];
int main(){
  int nCase = -1;
  int t = 0;
  while(cin >> nCase && nCase != 0){
    t++;
    for(int i = 0; i < nCase; i++){
        cin >> arr[i].x >> arr[i].y;
    }
    for(int i = 0; i < nCase; i++){
      for(int j = i + 1; j < nCase; j++){
        edge[i][j] = edge[j][i] = getDis(arr[i], arr[j]);
      }
    }
    for(int k = 0; k < nCase; k++){
      for(int i = 0; i < nCase; i++){
        for(int j = 0; j < nCase; j++){
          edge[i][j] = min(edge[i][j], max(edge[i][k], edge[k][j]));
        }
      }
    }
    cout << "Scenario #" << t << "\nFrog Distance = ";
    cout << fixed << setprecision(3) <<edge[0][1] << endl << endl;
  }
  return 0;
}

总结

在进行最短路变形问题求解的时候, 一定要搞明白松弛条件和数组的含义, 松弛条件不同, 数组的含义也不同.