Description

Input

Output

Sample Input

5
50
30 5
100 20 50
10 x x 10

Sample Output

35

解题思路：

	题意就是n台机器相互发送信息，要求从第一台机器，把剩下的n-1台都发送完所需的最小时间数。

	裸Dijkstra,用邻接矩阵存储。首先注意矩阵的初始化操作，主对角线赋值0，因为自己给自己发消息没意义，其他点设为无穷大。接下来比较奇葩的就是它的输入，它是按照下三角矩阵输入的，g[i][j] = g[j][i]，对称的两个点权值相同。如果输入为x，那么代表i到j没有边，保持无穷大。

	下面上模板，最后在求出的dis数组里遍历，寻找最大值，那个就是我们所求的最短所需时间。（这里有点别扭，可以这么理解，dis[i]代表src源点到i的最短时间，既然n个点都要遍历，那么时间数一定要大于等于dis里的最大值才可以）

	最后，输入处理那看到有人直接用函数做的······我函数知道的少就直接模拟转换了····感觉自己萌萌哒····

完整代码：

#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <climits>
#include <cassert>
#include <complex>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;

#pragma comment(linker, "/STACK:102400000,102400000")

typedef long long LL;
typedef double DB;
typedef unsigned uint;
typedef unsigned long long uLL;

/** Constant List .. **/ //{

const int MOD = int(1e9)+7;
const int INF = 0x3f3f3f3f;
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;
const DB EPS = 1e-9;
const DB OO = 1e20;
const DB PI = acos(-1.0); //M_PI;
int n;
string s;
int g[201][201];
int dis[201];
bool vis[201];
int res;

void init()
{
    for(int i = 1 ; i <= n ; i ++)
    {
        for(int j = 1; j <= n ; j ++)
        {
            if(i == j)
                g[i][j] = 0;
            else
                g[i][j] = INF;
        }
    }
}

void dijkstra()
{
    for(int i = 1 ; i <= n ; i ++)
    {
        dis[i] = INF;
    }
    dis[1] = 0;
    memset(vis , 0 , sizeof(vis));
    for(int i = 1; i <= n ; i ++)
    {
        int mark = -1;
        int mindis = INF;
        for(int j = 1 ; j <= n ; j ++)
        {
            if(!vis[j] && dis[j] < mindis)
            {
                mindis = dis[j];
                mark = j;
            }
        }
        vis[mark] = 1;
        for(int j = 1 ; j <= n ; j ++)
        {
            if(!vis[j])
            {
                dis[j] = min(dis[j] , dis[mark] + g[mark][j]);
            }
        }

    }
    res = -INF;
    for(int k = 1 ; k <= n ; k ++)
    {
        if(dis[k] > res)
            res = dis[k];
    }
}

int main()
{
    #ifdef DoubleQ
    freopen("in.txt","r",stdin);
    #endif
    while(~scanf("%d",&n))
    {
        init();
        for(int i = 2 ; i <= n ; i ++)
        {
            for(int j = 1 ; j < i ; j ++)
            {
                cin >> s;
                if(s == "x")
                    continue;
                else
                {
                    int sum = 0;
                    int jin = 1;
                    int len = s.length();
                    for(int k = len - 1 ; k >= 0 ; k --)
                    {
                        if(k != len - 1)
                            jin *= 10;
                        sum += jin * (s[k] - '0');
                    }
                    g[i][j] = sum;
                    g[j][i] = sum;
                }
            }
        }
        dijkstra();
        cout << res << endl;
    }
}

POJ1502（Dijkstra）