任意两点之间的最短路（floyed)

F、Moving On

Firdaws and Fatinah are living in a country with

Firdaws's home locates in the city

Input

The input contains several test cases, and the first line is a positive integer

For each test case, the first line contains two integers $10^4)q(1≤q≤2×104) which is the number of queries that will be given. The second line contains nn integers r_1, r_2, cdots , r_nr1,r2,⋯,rn indicating the risk of kidnapping or robbery in the city 11 to nn respectively. Each of the following nn lines contains nn integers, the jj-th one in the ii-th line of which, denoted by d_{i,j}di,j, is the distance from the city iito the city jj.$

Each of the following

We guarantee that $r_i le 10^5, 1 le d_{i,j} le 10^5 (i eq j), d_{i,i} = 01≤ri≤105,1≤di,j≤105(i�=j),di,i=0 and d_{i,j} = d_{j,i}di,j=dj,i. Besides, each query satisfies 1 le u,v le n1≤u,v≤n and 1 le w le 10^51≤w≤105.$

Output

For each test case, output a line containing Case #x: at first, where

输出时每行末尾的多余空格，不影响答案正确性

样例输入

样例输出

Case #1:
0
1
3
0
1
2

题意：输入t，表示t个测试样例
输入n,q,表示n个点，q次询问
下一行n个数表示[1,n]个点的危险值
接下来n行，每行3个数描述一条边，点x到y的距离为z;
最后q行，每行3个数，求从起点U到终点V,在每一个点危险值不超过W的前提下的最短距离

#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
#include<math.h>
#include<string>
#include<string.h>
#include<vector>
#include<utility>
#include<map>
#include<queue>
#include<set>
#define mx 0x3f3f3f3f
#define ll long long
#define MAXN 100
using namespace std;
int dp[250][250][250];//dp[k][i][j]表示 添加(第1~k小的危险值的城市后)的 i->j 最短路
int vis[250],rk[250];
bool cmp(int i,int j)
{
    return rk[i]<rk[j];
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int tt=1;tt<=t;tt++)
    {
        memset(dp,mx,sizeof(dp));
        int n,q;
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++)
        {
            vis[i]=i;//初始化排名
            scanf("%d",&rk[i]);
        }
        sort(vis+1,vis+n+1,cmp);//把城市的编号按风险等级从小到大排序，vis[排名]=编号
        // for(int i=1;i<=n;i++)
        //     cout<<vis[i]<<' ';
        // cout<<"<-----"<<endl;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",&dp[0][i][j]);//初始化每一条边的危险等级为0
        for(int k=1;k<=n;k++)
        {
            int now=vis[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][now]+dp[k-1][now][j]); 
            }

        }
        printf("Case #%d:
",tt);
        for(int i=1;i<=q;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            int k=0;
            for(int j=1;j<=n;j++)
                if(rk[vis[j]]<=w)//把危险值最接近w的边都加进去之后的最短路
                    k=j;
            printf("%d
",dp[k][u][v]);
        }
    }
    return 0;
}