题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstring>

using namespace std;

const int N = 105, M = 410;
int dist[N][N];
int g[N][N];
int n, m;

void floyid()
{
    for (int k = 1; k <= n; k ++)
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++)
                if (dist[i][j] > dist[i][k] + dist[k][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
        {
            if (i == j) dist[i][j] = 0;
            else dist[i][j] = 0x3f3f3f3f;
        }
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = dist[b][a] = min(dist[a][b], c);
    }

    floyid();

    int res = 0;
    for (int i = 2; i <= n; i ++) res = max(res, dist[1][i]);
    if (res == 0x3f3f3f3f) cout << -1;
    else cout << res;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla