Moving OnFirdaws and Fatinah are living in a country with nn cities, numbered from 11 to nn.Each city has a risk of kidnapping or robbery.Firdaws’s home locates in the city uu, and Fatinah’s home locates in the city vv.Now you are asked to find the shortest path from the city uu to the city vv that does not pass through any other city with the risk of kidnapping or robbery higher than ww, a threshold given by Firdaws.Input FormatThe input contains several test cases, and the first line is a positive integer TT indicating the number of test cases which is up to 5050.For each test case, the first line contains two integers n~(1\le n\le 200)n (1≤n≤200) which is the number of cities, and q~(1\le q\le 2\times 10^4)q (1≤q≤2×10 4 ) which is the number of queries that will be given.The second line contains nn integers r_1, r_2, \cdots, r_nr 1 ,r 2 ,⋯,r n 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}d i,j , is the distance from the city ii to the city jj.Each of the following qq lines gives an independent query with three integers u, vu,v and ww, which are described as above.We guarantee that 1\le r_i \le 10^51≤r i ≤10 5 , 1\le d_{i,j}\le 10^5~(i \neq j)1≤d i,j​ ≤10 5 (i ​ j), d_{i,i}0d i,i​ 0 and d_{i,j}d_{j,i}d i,j d j,i​ .Besides, each query satisfies 1\le u,v\le n1≤u,v≤n and 1\le w\le 10^51≤w≤10 5 .Output FormatFor each test case, output a line containing Case #x: at first, where xx is the test case number starting from 11.Each of the following qq lines contains an integer indicating the length of the shortest path of the corresponding query.样例输入1 3 6 1 2 3 0 1 3 1 0 1 3 1 0 1 1 1 1 2 1 1 3 1 1 1 2 1 2 2 1 3 2样例输出Case #1:013012题意每个城市由一定的危险值每次询问问在危险值不超过w的前提下最小的路径是多少不包括起点与终点分析由于存在200个点所以可以将其离散化一下这样就可以得到前n小的排序了那么定义dp[k][i][j]表示路过前k小城市从i到j的最小路径即可得到状态转移方程dp[k][i][j]min(dp[k-1][i][j],dp[k-1][i][id[k]]dp[k-1][id[k]][j]);参考https://blog.csdn.net/qq_40938077/article/details/81205540#includeiostream#includecstdio#includecstdlib#includealgorithm#includestring#includecmath#includecstring#includeset#includequeue#includestack#includemap#definerep(i,a,b) for(int ia;ib;i)typedeflonglongll;using namespace std;constintN20010;constintINF0x3f3f3f3f;vectorintve;inta[N],dp[N][N][N];intid[N],n,q;boolcmp(intx,inty){returna[x]a[y];}intmain(){// #ifndef ONLINE_JUDGE// freopen(in.txt,r,stdin);// #endif // ONLINE_JUDGEintT;scanf(%d,T);for(into1;oT;o){printf(Case #%d:\n,o);scanf(%d%d,n,q);memset(dp,INF,sizeofdp);for(inti1;in;i)scanf(%d,a[i]),id[i]i;for(inti1;in;i)for(intj1;jn;j)scanf(%d,dp[0][i][j]);sort(id1,id1n,cmp);// for(int i1;in;i)// coutid[i] ;// coutendl;for(intk1;kn;k){for(inti1;in;i){for(intj1;jn;j){dp[k][i][j]min(dp[k-1][i][j],dp[k-1][i][id[k]]dp[k-1][id[k]][j]);}}}intansINF;while(q--){intu,v,w;scanf(%d%d%d,u,v,w);ansINF;for(inti0;in;i)if(a[id[i]]w){ansmin(ans,dp[i][u][v]);}printf(%d\n,ans);}}return0;}