题意：求点1 到其他点的最短路径，然后取它们中的最大值即可
由于矩阵是对称的，所以题目只给了一个下三角矩阵。矩阵如下
12345105030100102500520x3305050x41002050010510xx10011313383NY_lv101502Accepted276K16MSC++1269B2013-03-05 11:28:10
View Code 1 #include <iostream> 2 #include <vector> 3 using namespace std; 4 5 #define MAX(a,b) ((a)>(b)?(a):(b)) 6 7 int matrix[105][105]; 8 bool visted[105]; 9 vector<int> dist; 10 int maxx; 11 12 void Dijkstra(int n) 13 { 14 int i, w; 15 maxx = -1; 16 dist.assign(n+1, INT_MAX); 17 dist[1] = 0; 18 19 memset(visted, false, sizeof(visted)); 20 21 while (true) 22 { 23 int minn = INT_MAX, v = 1; 24 for (i=1; i<=n; i++) //得到一个最短的权值 25 if (!visted[i] && minn > dist[i]) 26 minn = dist[i], v = i; 27 visted[v] = true; 28 if (minn == INT_MAX) 29 break; 30 31 for (w=1; w <=n; w++) 32 { 33 if (!visted[w] && matrix[v][w] < INT_MAX && dist[w] > dist[v] + matrix[v][w]) //逐一修改所有的路径使之趋近最短 34 dist[w] = dist[v] + matrix[v][w]; 35 } 36 //在最短权值中取得一个最大的 37 maxx=MAX(maxx,dist[v]); 38 } 39 } 40 41 int main() 42 { 43 int i, j, k; 44 int n; 45 char str[100]; 46 while (scanf("%d",&n) != EOF) 47 { 48 memset(matrix, 0, sizeof(matrix)); 49 for (i=2; i<=n; i++) 50 { 51 for (j=1; j<i; j++) 52 { 53 scanf("%s", &str); 54 if (str[0] == 'x') 55 matrix[i][j] = INT_MAX; 56 else 57 { 58 int len = strlen(str); 59 for (k=0; k<len; k++) 60 { 61 matrix[i][j] *= 10; 62 matrix[i][j] += str[k] - '0'; 63 } 64 } 65 matrix[j][i] = matrix[i][j]; 66 } 67 } 68 Dijkstra(n); 69 cout<<maxx<<endl; 70 } 71 return 0; 72 }
转载于:https://www.cnblogs.com/lv-2012/archive/2013/03/05/2944038.html
相关资源：JAVA上百实例源码以及开源项目