链接：https://vjudge.net/problem/POJ-2253
题意：
给n个点，求1->2的路径的每段路中的最大值的最短路。
思路：
刚开始看不懂题。看了题解后看明白的。
直接Dijkstra算法，Dis数组保存到每点路径中的路段的最大值。
代码：
#include#include #include #include #include #include #include using namespace std;const int MAXN = 200+10;double Map[MAXN][MAXN];double Dis[MAXN];int Vis[MAXN];int n;struct Node{ double _x; double _y;}node[MAXN];double get_Len(Node a,Node b){ return sqrt((a._x-b._x)*(a._x-b._x) + (a._y-b._y)*(a._y-b._y));}double Dijkstra(){ memset(Dis,0, sizeof(Dis)); memset(Vis,0, sizeof(Vis)); for (int i = 2;i<=n;i++) { Dis[i] = Map[1][i]; } Vis[1] = 1; for (int i = 1;i<=n;i++) { int w; double small = 9999999.0; for (int j = 1; j <= n; j++) { if (Vis[j] == 0 && small > Dis[j]) { w = j; small = Dis[j]; } } Vis[w] = 1; if (w == 2) return small; for (int j = 1; j <= n; j++) { if (Vis[j] == 0) { //double now = max(small,Map[w][j]); //if (now < Dis[j]) //Dis[j] = now; Dis[j] = min(Dis[j], max(small, Map[w][j])); } } }}int main(){ int cnt = 0; while (cin >> n && n) { for (int i = 1;i<=n;i++) { cin >> node[i]._x; cin >> node[i]._y; } for (int i = 1;i<=n;i++) for (int j = 1;j<=n;j++) Map[i][j] = Map[j][i] = get_Len(node[i],node[j]); double v = Dijkstra(); if (cnt != 0) printf("\n"); printf("Scenario #%d\nFrog Distance = %.3f\n",++cnt,v); }}