C++14 解法, 执行用时: 4ms, 内存消耗: 388KB, 提交时间: 2020-07-29

#include<stdio.h>
#include<string.h>
#define INF 0x3fffffff
const int maxn = 104;
int G[maxn][maxn], vis[maxn], d[maxn];
int n, k;
void Dijkstra(int s) {
    d[s] = 0;
    for(int i = 0; i < n; i++) {
        int u = -1, mind = INF;
        for(int j = 1; j <= n; j++) {
            if(!vis[j] && mind > d[j]) {
                mind = d[j];
                u = j;
            }
        }
        if(u == -1)
            return;
        vis[u] = 1;
        for(int v = 1; v <= n; v++) {
            if(!vis[v]&&G[u][v] != INF && d[v] > d[u] + G[u][v])
                d[v] = d[u] + G[u][v];
        }
    }
}
int main() {
   // freopen("input.txt", "r", stdin);
    // freopen("input.txt", "a", stdout);
    for(int i = 0; i < maxn; i++)
        for(int j = 0; j < maxn; j++) {
            if(i == j)
                G[i][j] = 0;
            else
                G[i][j] = INF;
        }
    char c = getchar();
    int u, v, x;
    while(c != ']') {
        scanf("[%d,%d,%d]", &u, &v, &x);
        if(u != v && x < G[u][v]) {
            G[u][v]= x;
        }
        c = getchar();
    }
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) {
        vis[i] = 0;
        d[i] = INF;
    }
    Dijkstra(k);
    int maxt=d[k];
    for(int i=1;i<=n;i++){
        if(maxt<d[i])
            maxt=d[i];
    }
    if(maxt==INF)
        printf("-1");
    else
        printf("%d",maxt);
    return 0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 476KB, 提交时间: 2020-10-29

#include <bits/stdc++.h>
using namespace std;

int N, K, G[101][101], dis[101];
bool vis[101];

void dijkstra(int s){
    dis[s] = 0;
    for(int i=0;i<N;i++){
        int k=0, Min=INT_MAX;
        for(int j=1;j<=N;j++){
            if(!vis[j] && dis[j]<Min){
                Min = dis[j];
                k = j;
            }
        }
        if(k==0)
            break;
        vis[k] = true;
        for(int v=1;v<=N;v++){
            if(!vis[v] && G[k][v]!=INT_MAX && dis[v]>dis[k]+G[k][v])
                dis[v] = dis[k] + G[k][v];
        }
    }
}

int main(){
    int s, d, t, Max=0;
    memset(vis, false, sizeof(vis));
    for(int i=0;i<101;i++){
        dis[i] = INT_MAX;
        for(int j=0;j<101;j++){
            if(i==j)
                G[i][j] = 0;
            else
                G[i][j] = INT_MAX;
        }
    }
    char c = getchar();
    while(c!=']'){
        scanf("[%d,%d,%d]", &s, &d, &t);
        if(s!=d && t<G[s][d])
            G[s][d] = t;
        c = getchar();
    }
    scanf("%d%d", &N, &K);
    dijkstra(K);
    for(int i=1;i<=N;i++)
        Max = max(Max, dis[i]);
    if(Max==INT_MAX)
        printf("-1\n");
    else
        printf("%d\n", Max);
    return 0;
}