gym-102222-F（moving on）-floyd

题意：给你一个图，图中每个点有对应的危险值，q个询问，每个询问给出起点，终点，限制值，需要你计算出从起点走到终点不走那些危险值超过限制值的最短路；（起点和终点的危险值不算）

解题思路：一开始看题目给了10s，想的是用d每次询问跑一遍dij，在dij里面+一个限制，但超时了（讲道理，感觉10s够啊）。。。然后看别人的解法使用三维floyd解决的，dp[k][i][j]，k表示用完危险值排名为k的点松弛后的当前最短路的值

代码：

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int id;
    int val;
}a[250];
const int inf=0x3f3f3f3f;
int dp[250][250][250];
int n,m,t,cnt;
int x,y,w;
bool cmp(node a,node b)
{
    return a.val<b.val;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        memset(dp,inf,sizeof(dp));
        scanf("%d%d",&n,&m);cnt++;
        for(int i=1;i<=n;i++)
            a[i].id=i;
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i].val);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",&dp[0][i][j]);
        sort(a+1,a+1+n,cmp);//按危险值排序
        for(int k=1;k<=n;k++)
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][a[k].id]+dp[k-1][a[k].id][j]);
                }
            }
        }//floyd
        printf("Case #%d:
",cnt);
        while(m--)
        {
            scanf("%d%d%d",&x,&y,&w);
            int pos=0;
            for(int i=1;i<=n;i++)
            {
                if(a[i].val<=w)
                    pos=i;//找到对应在哪个危险值的点结束
            }
            printf("%d
",dp[pos][x][y]);
        }
    }
}