The 2018 ACM-ICPC Chinese Collegiate Programming Contest Moving On

Firdaws and Fatinah are living in a country with

Firdaws's home locates in the city

Input Format

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 nnlines 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 ii to the city jj.$

Each of the following

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

Output Format

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

样例输入

样例输出

Case #1:
0
1
3
0
1
2

题目来源

The 2018 ACM-ICPC Chinese Collegiate Programming Contest

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <string>
 5 #include <algorithm>
 6 #include <utility>
 7 #include <vector>
 8 #include <map>
 9 #include <queue>
10 #include <stack>
11 #include <cstdlib>
12 #include <cmath>
13 typedef long long ll;
14 #define lowbit(x) (x&(-x))
15 #define ls l,m,rt<<1
16 #define rs m+1,r,rt<<1|1
17 using namespace std;
18 #define pi acos(-1)
19 const int N=250;
20 const int inf=0x3f3f3f3f;
21 int r[N],f[N][N][N];
22 int  t,n,q;
23 int id[N];
24 void solve(int n){
25     for(int k=1;k<=n;k++){
26         int kk=id[k];//实际顺序
27         for(int i=1;i<=n;i++){
28             for(int j=1;j<=n;j++){
29                 f[k][i][j]=min(f[k-1][i][j],f[k-1][i][kk]+f[k-1][kk][j]);
30             }
31         }
32     }
33 }
34 bool cmp(int i,int j){
35     return  r[i]<r[j];
36 }
37 int main()
38 {
39     scanf("%d",&t);
40     int i;
41     for(i=1;i<=t;i++){
42         scanf("%d%d",&n,&q);
43         for(int j=1;j<=n;j++){
44             id[j]=j;
45             scanf("%d",&r[j]);
46         }
47         memset(f,inf,sizeof(f));
48         for(int k1=1;k1<=n;k1++){
49             for(int k2=1;k2<=n;k2++){
50                 scanf("%d",&f[0][k1][k2]);
51             }
52         }
53         sort(id+1,id+n+1,cmp);//按照r[]从小到大排序，为了solve()
54         sort(r+1,r+n+1);//为了找符合条件的k4
55         solve(n);
56         printf("Case #%d:
",i);
57         int u,v,w;
58          for(int k3=1;k3<=q;k3++){
59              scanf("%d%d%d",&u,&v,&w);
60              int k4;
61              for(k4=1;k4<=n;k4++){
62                  if(r[k4]>w){
63                      break;
64                  }
65              }
66              printf("%d
",f[k4-1][u][v]);         
67          }
68     }
69     return  0;
70 }