链接：https://vjudge.net/problem/POJ-1502

题意：

n个点，从1号向开始选择任意个结点发送信息，下一个结点接收到信息后可再向任意个结点发送。

同时发送信息有时间代价。代价有邻接矩阵给出。只给出坐下全部，x为不连通。

同时为无向的。即a->b == b->a。

求每个结点都接受到信息的最小时间代价。

思路：

Dijkstra，求Dis数组中的最大值

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int MAXN = 100+10;int Map[MAXN][MAXN];int Dis[MAXN];int Vis[MAXN];int main(){    int n;    scanf("%d",&n);    for (int i = 1;i<=n;i++)        for (int j = 1;j<=n;j++)            if (i == j)                Map[i][j] = 0;            else                Map[i][j] = 999999;    for (int i = 2;i<=n;i++)        for (int j = 1;j
          
           > x; if (x[0] != 'x') { istringstream iss(x); int num; iss >> num; Map[i][j] = Map[j][i] = num; } } for (int i = 1;i<=n;i++) Dis[i] = Map[1][i]; Vis[1] = 1; for (int i = 1;i<=n;i++) { int w = -1,small = 999999; for (int j = 1;j<=n;j++) if (Vis[j] == 0&&Dis[j] < small) { w = j; small = Dis[j]; } Vis[w] = 1; for (int j = 1;j<=n;j++) { if (Vis[j] == 0) { Dis[j] = min(Dis[j],Dis[w]+Map[w][j]); //cout << Dis[j] << ' ' << Dis[w] + Map[w][j] << endl; } } } int sum = 0; for (int i = 2;i<=n;i++) sum = max(sum,Dis[i]); cout << sum << endl; return 0;}/*410x 10x x 10 */