UVA423 MPI Maelstrom题解

_NTT_ · 2021-10-09 17:54:39 · 题解

题意简化

给定半个 n \times n 的邻接矩阵，让你求 max \{ dis[1][i] \} (2 \leq i \leq n )

思路

最短路的模板题，由于 n \leq 100，使用 n^3的Floyd算法可以过

代码

代码如下：

#include <iostream>
#include <queue>
#include <cstring>

#define int long long//int有可能爆掉

using namespace std;

const int INF = 0x3f3f3f3f;//赋值成极大值

inline int read() {//快读
    int x = 0; char c = getchar();
    while(c < '0' || c > '9') if(c == 'x') return INF; else c = getchar(); //若c为x，则表示不可走，复制成INF来表示
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - '0', c = getchar();

    return x;
}

int n = read(), dis[105][105];

signed main() {//使用了宏定义，这里只能用signed
    for(int i = 2 ;i <= n ;++i) for(int j = 1 ;j < i ;++j) dis[i][j] = dis[j][i] = read();//无向图读入

    for(int k = 1 ;k <= n ;++k)//枚举中间点
        for(int i = 1 ;i <= n ;++i)
            for(int j = 1 ;j <= n ;++j)
                if(dis[i][j] > dis[i][k] + dis[k][j])//若从i->k的距离+k->j的距离小于i->j的距离，那么使用这个值来更新dis[i][j]
                    dis[j][i] = dis[i][j] = dis[i][k] + dis[k][j];//无向图dis[i][j]和dis[j][i]一起更新

    int res = -1;//复制成-1一定会被更新
    for(int i = 1 ;i <= n ;++i) res = max(res, dis[1][i]);
    cout << res << endl;//输出

    return 0;
}