Moving On Gym

题意：

给出一张完全图，(n) 个点，任意两点间距离已知，由矩阵 (d) 给出。每个点有一个权重 (r)。
有 (q) 次询问，每次问从点 (u) 到点 (v) 的，满足不经过点权大于 (w) 的点的最短路径长度。

数据范围：
(1leq T leq50,1≤n≤200,1≤q≤2×10^4,1≤r_i≤10^5,1≤d_{i,j}≤10^5(i≠j),d_{i,i}=0;and;d_{i,j}=d_{j,i},1≤u,v≤n;and;1≤w≤10^5)

分析：

一开始用 (q) 次迪杰特斯拉，复杂度：(O(T*q*nlogn))，以为能卡过，结果果断 (t)。
正解：
  (Floyd) 的深度理解。(Floyd) 的算法中，会用第三个点来更新两个点之间的最短距离，即松弛。用 (dis[k][i][j]) 表示用前 (k) 个点松弛后，任意两点 (i,j) 之间的最短距离。由此，我们可以想到（当然没想到），如果选择点权没有超过 (w) 的点来更新任意点的最短距离，那么问题不就解决了吗。只要把点权从小到大进行排序，依次用来松弛，询问时，对应输出即可。
复杂度：(O(T*n^3))

代码：

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ft first
#define sd second
typedef pair<int,int>P;
const int N=210;
const int inf=0x3f3f3f3f;
int dis[N][N][N];
P point[N];
void read(int &x)
{
    x=0;
    int f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    x*=f;
}
void init(int n)
{
    sort(point+1,point+1+n);
    for(int k=1;k<=n;k++)//排序后的前k个点
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dis[k][i][j]=dis[k-1][i][j];
                if(dis[k-1][i][point[k].sd]+dis[k-1][point[k].sd][j]<dis[k][i][j])
                    dis[k][i][j]=dis[k-1][i][point[k].sd]+dis[k-1][point[k].sd][j];
            }
        }
    }
}
int main()
{
    int t,q,n,cot=0;
    read(t);
    while(t--)
    {
        int u,v,w;
        read(n);
        read(q);
        for(int i=1;i<=n;i++)
        {
            read(point[i].ft);
            point[i].sd=i;
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                read(dis[0][i][j]);
        init(n);
        printf("Case #%d:
",++cot);
        while(q--)
        {
            read(u);
            read(v);
            read(w);
            int ans=dis[0][u][v];
            for(int i=1;i<=n;i++)
            {
                if(point[i].ft>w)
                    break;
                ans=min(dis[i][u][v],ans);
            }
            printf("%d
",ans);
        }
    }
    return 0;
}