图论——最短路(2)

Floyd算法可在任意权图中求多源最短路，时间复杂度为O(n^3)，适用于n较小的情况。以P2910为例。

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<int> a(m+1);
    for(int i=1;i<=m;++i){
        cin>>a[i];
    }
    vector<vector<int>> dis(n+1,vector<int>(n+1));
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cin>>dis[i][j];
        }
    }
    for(int k=1;k<=n;++k){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
    int ans=0;
    for(int i=1;i<=m-1;++i){
        ans+=dis[a[i]][a[i+1]];
    }
    cout<<ans;
}