题解 | #仓库配送#

1. 邻接表
2. floyd算法
3. 注意初始化INT_MAX。表示点和点之间不可达。
4. 最后就是从起送点到所有目的地的最长时间（可以理解为一种并行的思想，最长的那个最短，决定送完）

#include<bits/stdc++.h>

using namespace std;

//算出点到点之间的最小路径
int floyd(vector<vector<int>> graph, int N, int source){
    for(int k =1; k<= N; k++){
        for(int i =1; i<= N;i++){
            for(int j =1; j<= N;j++){
                if(graph[i][k]!= INT_MAX && graph[k][j] !=INT_MAX ){
                    graph[i][j] = min(graph[i][j],graph[i][k]+graph[k][j]);
                }
            }
        }
    }

    int max_ =INT_MIN;

    //最小路径中最大的就是最短完成时间。
    for(int i = 1; i<= N;i++){
        max_ = max(max_,graph[source][i]);
    }
    if(max_==INT_MAX) return -1;
    return max_;


}


int main(){

    int N,K,M;
    cin>>N>>K>>M;

    int v,u,w;

    vector<vector<int>> graph(N+1,vector<int>(N+1,INT_MAX));//全部默认不可达

    for(int i=0; i< M;i++){//M组数据
        cin>>v>>u>>w;
        graph[v][u] = w;
    }

    for(int i=1; i<= N;i++){//对角线要为1
        graph[i][i] = 0;
    }

    cout<<floyd(graph,N,K)<<endl;


    return 0;
}