算法日记19：SC71多元最短路(Floyd)

一、题目：

二、题解：

1、我们一眼就可以看出这是一道多源最短路的题目，因此直接套用Floyd模板即可

2、Floyd原理解析

2.1：假设现在我们有这样一个图，要求我们求任意两个顶点的距离

2.2：对于这个样例，我们使用Floyd来做的步骤如下：（顺序不能改变！！）

• 其中，我们并不关心两个点之间是怎么连接的，仅仅只是枚举所有情况，查看是否有其他情况使得两个点之间的路径更小
  

2.3：也就是意味着我们要使用$O$(n³)的时间复杂度，因此点/边的数量级一般<1e3

我们并不证明公式的正确性，背下模板即可

三、完整代码如下：

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

typedef long long ll;
const int N=307;
ll dis[N][N];  //表示从i-->j的距离

void solve()
{
    ll n,m,q;cin>>n>>m>>q;
    memset(dis,0x3f,sizeof(dis));

    for(int i=1;i<=m;i++)
    {
        ll ui,vi,wi;cin>>ui>>vi>>wi;
        dis[ui][vi]=min(dis[ui][vi],wi);    //对重边/自环的处理
    }
    //初始化
    for(int i=1;i<=n;i++) dis[i][i]=0;

    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]);

    while(q--)  //q次询问
    {
        ll ui,vi;cin>>ui>>vi;
        if(dis[ui][vi]>=4e18)   cout<<-1<<'\n';
        else cout<<dis[ui][vi]<<'\n';
    }
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int _=1;
    while(_--)solve();
    return 0;
}