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

一.题目链接：

二.题目大意：

有 n 个城市，q 次询问.

给出每个城市的危险度 r 和 城市的邻接矩阵.

每次询问给出 u、v、w，求从 u 到 v 且不经过其他危险度超过 w 的城市的最短路.

三.分析：

一开始直接跑 q 次 spfa，这时限不应该 T 啊...

正解是 floyd 变形.

在最初的 floyd 的 d 数组中 d[i][j] 表示在前 k 的点参与下，d[i][j] 的最短路径.

利用这一性质，我们不妨先将 r 数组排序，这样 d[i][j] 则表示在前 k 小危险程度的点参与下，d[i][j] 的最短路.

详见代码.

四.代码实现：

#include 
   
    using namespace std;const int M = (int)2e2;struct node1{    int r, id;}R[M + 5];struct node2{    int u, v, w, id;}Q[M * M + 5];int ans[M * M + 5];int d[M + 5][M + 5];bool cmpR(node1 a, node1 b){    return a.r < b.r;}bool cmpQ(node2 a, node2 b){    return a.w < b.w;}int main(){    int T;    scanf("%d", &T);    for(int ca = 1; ca <= T; ++ca)    {        int n, q;        scanf("%d %d", &n, &q);        for(int i = 1; i <= n; ++i)        {            scanf("%d", &R[i].r);            R[i].id = i;        }        for(int i = 1; i <= n; ++i)            for(int j = 1; j <= n; ++j)                scanf("%d", &d[i][j]);        for(int i = 1; i <= q; ++i)        {            scanf("%d %d %d", &Q[i].u, &Q[i].v, &Q[i].w);            Q[i].id = i;        }        sort(R + 1, R + n + 1, cmpR);        sort(Q + 1, Q + q + 1, cmpQ);        int pos = 1;        for(int _q = 1; _q <= q; ++_q)        {            while(pos <= n && R[pos].r <= Q[_q].w)            {                int k = R[pos].id;                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]);                    }                }                ++pos;            }            ans[Q[_q].id] = d[Q[_q].u][Q[_q].v];        }        printf("Case #%d:\n", ca);        for(int i = 1; i <= q; ++i)            printf("%d\n", ans[i]);    }    return 0;}