http://poj.org/problem?id=1502
题意：这是一个下三角，上三角跟下三角图形一致，（若是完整的矩阵的话， 相当于 Map[i][j] 的距离为相对应的数值）这道题也一样。 不同的是 若 显示的为 ‘x’字母时， 说明Map[i][j]为正无穷， 两个点之间不通。 现在的问题是：求1到2， 1到3， .... 1到n 之中哪条路是最短的。
****
英语真的是太渣，表示看懂题意不是一般的难啊， 但是看懂题意后真的好简单 %>_<% 。。
不要再考我英语了，我诚实的说四级还没过 %>_<%。。。
#include<stdio.h> #include<string.h> #include<math.h> #include<queue> #include<algorithm> using namespace std; #define maxn 110 #define oo 0x3f3f3f3f int maps[maxn][maxn], v[maxn], dist[maxn]; int n; void Init() { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(i==j) maps[i][j] = 0; else maps[i][j] = maps[j][i] = oo; } } } void Dij() { memset(v, 0, sizeof(v)); memset(dist, 0, sizeof(dist)); for(int i=1; i<=n; i++) dist[i] = maps[1][i]; v[1] = 1; for(int i=1; i<n; i++) { int index, mins = oo; for(int j=1; j<=n; j++) { if(!v[j] && dist[j] <mins) { index = j; mins = dist[j]; } } v[index] = 1; for(int j=1; j<=n; j++) { if(dist[j] > mins + maps[index][j] && !v[j]) dist[j] = mins + maps[index][j]; } } int ans = 0; for(int i=1; i<=n; i++) ans = max(ans, dist[i]); printf("%d\n", ans); } int main() { char str[maxn]; int num; while(scanf("%d", &n)!=EOF) { Init(); for(int i=2; i<=n; i++) { for(int j=1; j<i; j++) { scanf("%s", str); if(str[0] != ‘x‘) { sscanf(str, "%d", &num); maps[i][j] = maps[j][i] = min(maps[i][j], num); } } } Dij(); } return 0; }
原文：http://www.cnblogs.com/daydayupacm/p/5698105.html
