POJ1502---MPI Maelstrom
链接
题意理解：
前面一大坨不用看，题意就是给个无向图，求从第一个目标到所有目标的最短路的最大值（给所有的目标发完信息）。给了下半个矩阵，顺其自然用邻接矩阵表示，然后利用Dijkstra算法求出最短路即可。
AC代码：
#include<iostream>
#include<cstdio>
#include<ctype.h>
#include<string>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int n;
int cost[105][105];
int d[105];
bool used[105];void dijkstra(int s)
{fill(d, d + n+1, INF);fill(used, used + n+1, false);d[s] = 0;while (1){int v = -1;//从尚未使用的顶点中选择一个距离最小的顶点for (int u = 1; u <= n; u++){if (!used[u] && (v == -1 || d[u] < d[v]))v = u;}if (v == -1)break;//没找着。used[v] = true;for (int u = 1; u <= n; u++)//对 和v相连的点u，更新d[u]，也是dj算法的核心（贪心），d[u] = min(d[u], d[v] + cost[v][u]);
//扫描所有的顶点，cost为INF代表没有边，走完循环d中的值还是INF，cost不为INF的就是有边咯，更新d即可。}
}int main()
{int x;while (cin >> n){for (int i = 1; i <= n; i++)cost[i][i] = 0;for(int i=2;i<=n;i++)for (int j = 1; j < i; j++){ if (scanf("%d", &x))cost[i][j] = cost[j][i] = x;else {getchar();//吸收字符xcost[i][j] = cost[j][i] = INF;}}dijkstra(1);int ans = d[1];for (int i = 2; i <= n; i++)ans = max(ans, d[i]);cout << ans << endl;}
}