本文共 1253 字，大约阅读时间需要 4 分钟。

题目描述：

给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定k个询问，每个询问包含两个整数x和y，表示查询从点x到点y的最短距离，如果路径不存在，则输出“impossible”。

数据保证图中不存在负权回路。

输入格式

第一行包含三个整数n，m，k

接下来m行，每行包含三个整数x，y，z，表示点x和点y之间存在一条有向边，边长为z。

接下来k行，每行包含两个整数x，y，表示询问点x到点y的最短距离。

输出格式

共k行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出“impossible”。

数据范围

1≤n≤200,

输入样例：

3 3 21 2 12 3 21 3 12 11 3

输出样例：

impossible1

分析：

多源最短路问题，采用Floyd算法，时间复杂度为O(n^3)。

Floyd算法的思想是动态规划。设d[i][j]表示i点到j点的最短距离，i点到j点中间经过某点k，则状态转移方程为d[i][j] = min(d[i][k] + d[k][j],d[i][j])（1<=k<=n);然后用三重循环实现该状态扩散的过程即可。注意对中间节点k的枚举需要放在循环的最外层，否则会出错。

#include 
   
    #include 
    
     #include 
     
      using namespace std;const int maxn = 205;int d[maxn][maxn],n,m,k;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][k] + d[k][j],d[i][j]);}int main(){    scanf("%d%d%d",&n,&m,&k);    int x,y,z;    memset(d,0x3f,sizeof d);    for(int i = 1;i <= n;i++)   d[i][i] = 0;    for(int i = 0;i < m;i++){        scanf("%d%d%d",&x,&y,&z);        d[x][y] = min(d[x][y],z);    }    floyd();    while(k--){        scanf("%d%d",&x,&y);        if(d[x][y] > 0x3f3f3f3f / 2)    puts("impossible");        else printf("%d\n",d[x][y]);    }    return 0;}
     
    
   

转载地址：https://blog.csdn.net/qq_30277239/article/details/101062266 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！