$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$

思路：

1. floyd算法基于dp的思想，后续dp章节时我会细说
2. 存在负权边，所以判断时，应 d[a][b] > INF / 2 
3. 用邻接矩阵来存边，有重边则取较小边

完整代码（多源汇最短路问题）

#include<bits/stdc++.h>

using namespace std;

const int N = 210, INF = 0x3f3f3f3f;

int n,m,q;
int d[N][N];

void floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}

int main()
{
    cin>>n>>m>>q;

    //初始化d数组
    memset(d,0x3f,sizeof d);
    for(int i=1;i<=n;i++) d[i][i]=0;

    //邻接矩阵，取权值较小的边
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        d[a][b]=min(d[a][b],c);
    }

    floyd();

    while(q--)
    {
        int a,b;
        cin>>a>>b;

        if(d[a][b]>INF/2) cout<<"impossible"<<endl;
        else cout<<d[a][b]<<endl;
    }

    return 0;
}