poj1502MPI Maelstrom

题意：
给你一个不完全的矩阵，数字表示权值，x表示两点间不可达
由于自身到自身花费的时间为0，所以没有给出，由于i到j和j到i距离相同，互达时间相同
所以只给出了一半的临界矩阵。
根据给你的这个临界矩阵，让你来求从点1到其他点所花费最短时间集里面的的最大值。
其实这是一个很直接的最短路

 1 #include <iostream>
 2 #include <cstring>
 3 #include <stdio.h>
 4 #include <string.h>
 5 #include <stdlib.h>
 6 using namespace std;
 7 int n,m;
 8 int map[110][110],dis[110],visited[110];
 9 const int inf=0x3f3f3f3f;
10 void Dijkstra()
11 {
12     int min,i,j,pos,maxx;
13     memset(visited,0,sizeof(visited));
14     for(i=1;i<=n;i++)
15     {
16         dis[i]=map[1][i];
17     }
18     visited[1]=1;
19     for(i=1;i<n;i++)
20     {
21         min = inf;
22         for(j=1;j<=n;j++)
23         {
24             if(dis[j]<min&&!visited[j])
25             {
26                 pos=j;
27                 min=dis[j];
28             }
29         }
30         visited[pos]=1;
31         for(j=1;j<=n;j++)
32         {
33             if(!visited[j]&&dis[pos]+map[pos][j]<dis[j])
34                 dis[j]=dis[pos]+map[pos][j];
35         }
36     }
37     maxx=0;
38     for(int i=2;i<=n;i++)
39     {
40         maxx=max(maxx,dis[i]);
41     }
42     cout<<maxx<<endl;
43 }
44 int main()
45 {
46     int j,i;
47     char s[10];
48     while(~scanf("%d",&n))
49     {
50         for(i=1;i<=n;i++)
51         {
52             for(j=1;j<=n;j++)
53             map[i][j]=inf;
54             map[i][i]=0;
55         }
56         for(int i=2;i<=n;i++)
57         for(int j=1;j<i;j++)
58         {
59             scanf("%s",s);
60             if(s[0]!='x')
61             map[i][j]=map[j][i]=atoi(s);
62         }
63         Dijkstra();
64     }
65     return 0;
66 }