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

为了解决问题，我们需要找到从点x到点y的最短距离，如果不存在路径则输出“impossible”。我们将使用Floyd-Warshall算法来解决这个问题。Floyd-Warshall算法能够处理有向图中的最短路径问题，特别是处理负权重的情况，适用于本题的情况。

方法思路

解决代码

#include 
   
    #include 
    
     #include 
     
      using namespace std;int main() {    int n, m, k;    scanf("%d %d %d", &n, &m, &k);        int INF = 1 << 30;    int d[n+1][n+1];    for (int i=1; i<=n; i++) {        for (int j=1; j<=n; j++) {            d[i][j] = INF;        }        d[i][i] = 0;    }        for (int i=1; i<=m; i++) {        int x, y, z;        scanf("%d %d %d", &x, &y, &z);        if (d[x][y] > z) {            d[x][y] = z;        }    }        // Floyd-Warshall算法    for (int k=1; k<=n; k++) {        for (int i=1; i<=n; i++) {            for (int j=1; j<=n; j++) {                if (d[i][j] > d[i][k] + d[k][j]) {                    d[i][j] = d[i][k] + d[k][j];                }            }        }    }        while(k--) {        int x, y;        scanf("%d %d", &x, &y);        if (d[x][y] == INF) {            puts("impossible");        } else {            puts(to_string(d[x][y]));        }    }        return 0;}
     
    
   

代码解释