https://nanti.jisuanke.com/t/41290

題干：

Firdaws 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

The input contains several test cases, and the first line is a positive integer?TTindicating the number of test cases which is up to?5050.

For each test case, the first line contains two integers?n?(1≤n≤200)n?(1≤n≤200)?which is the number of cities, and?q?(1≤q≤2×104)q?(1≤q≤2×104)?which is the number of queries that will be given. The second line contains?nn?integers?r1,r2,?,rnr1,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?di,jdi,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≤ri≤1051≤ri≤105,?1≤di,j≤105?(i≠j)1≤di,j≤105?(i≠j),?di,i=0di,i=0?and?di,j=dj,idi,j=dj,i. Besides, each query satisfies?1≤u,v≤n1≤u,v≤n?and?1≤w≤1051≤w≤105.

Output

For each test case, output a line containing?Case #x:?at first, where?x?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.

Example

Input

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

Output

Case #1: 0 1 3 0 1 2

題目大意：

給你一個n個點的有向完全圖，每個點有點權ri，有Q組 詢問，每次詢問給出三個參數u,v,w，要求u到v的最短路，且要求途徑的點的點權不能超過w（也就是點的點權<=w），讓你輸出這個最短路的權值。（n<=200,w<=1e5,q<=2e4）

解題報告：

考慮到n只有200，考慮FLoyd。又因為給定的w雖然有2e4個（每一個詢問可能都對應一個w），但是對應到n個點上，其實可以縮點縮成200個權值，再考慮Floyd的性質，是前i個點的前提下進行的，所以直接改一改點的編號順序（按照r排序），然后離線搞一搞就行了。把更新均攤到n個點中。

這題的標解是對r排序后做三維的Floyd，相當于每個版本都記錄下來了這樣可以在線做，對于每個詢問，直接二分查找下標，然后輸出結果就行了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; struct Node {int r,id;bool operator<(const Node & b)const {return r < b.r;} } R[MAX]; struct Nodee {int st,ed,w,id;bool operator<(const Nodee & b)const {return w < b.w;} } q[MAX]; int n,Q; int d[222][222],ans[MAX]; int main() {int T,iCase=0;cin>>T;while(T--) {scanf("%d%d",&n,&Q);for(int i = 1; i<=n; i++) scanf("%d",&R[i].r),R[i].id = i;for(int i = 1; i<=n; i++) {for(int j = 1; j<=n; j++) scanf("%d",&d[i][j]);}for(int u,v,w,i = 1; i<=Q; i++) {scanf("%d%d%d",&q[i].st,&q[i].ed,&q[i].w);q[i].id = i;}sort(R+1,R+n+1);sort(q+1,q+Q+1);int cur = 1,curw = 0;for(int i = 1; i<=Q; i++) {while(cur <= n && q[i].w >= R[cur].r) {int k = R[cur].id;for(int i = 1; i<=n; i++) {for(int j = 1; j<=n; j++) d[i][j] = min(d[i][j],d[i][k] + d[k][j]);}cur++;}ans[q[i].id] = d[q[i].st][q[i].ed];}printf("Case #%d:\n",++iCase);for(int i = 1; i<=Q; i++) printf("%d\n",ans[i]);}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【2018icpc宁夏邀请赛现场赛】【Gym - 102222F】Moving On（Floyd变形，思维，离线处理）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。