多源汇最短路问题（询问多个不同结点之间的最短距离）

使用Floyd算法

时间复杂度0(n ^ 3);

代码

# include <iostream>
# include <cstring>
using namespace std;
const int N = 210;

int g[N][N];


int n,m,k;

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

int main()
{
    scanf("%d %d %d",&n,&m,&k);
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j =1 ; j <= n ; j++)
        {
            if(i == j)
            {
                g[i][j] = 0;
            }
            else
            {
                g[i][j] = 0x3f3f3f3f;
            }
        }
    }

    for(int i = 0 ; i < m ; i++)
    {
        int a,b,w;
        scanf("%d %d %d",&a,&b,&w);
        g[a][b] = min(g[a][b] , w);
    }

    floyd();

    while(k--)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        if(g[a][b] >= 0x3f3f3f3f / 2)  //与之前的bellman_ford算法类似，如果某个结点由源点到不了，但是某些其他结点可以到达，并且为负值，则g[a][b]会减少。而不等于 0x3f3f3f3f.
        {
            printf("impossible\n");
        }
        else
        {
            printf("%d\n",g[a][b]);
        }
    }
    return 0;
}