最近做了兩道floyd變種的題目,又加深了對floyd原理的理解.
第2題: tju 3214 Find the Path
http://acm.tju.edu.cn/toj/showp3214.html
題目大意是給一個無向圖,每個結點有個點權c[p]
對于查詢的點對i,j和權k,求在中間節點(不包含端點i,j)權值不大于k的限制下,i,j間最短路徑.
由于查詢次數多,因此一次查詢復雜度需要在O(logn)以內.考慮計算出所有點對在所有限制條件下的最短路,O(1)查詢.
限制條件不作用于端點i,j,正好可以用floyd解決.因為floyd正是不斷向中間點集中加入點.只要限制一下這些被加入點的條件,就可以解決這題了.
初步歸納,對于查詢i,j,k,應該輸出將所有c[p]<=k的點加入后的floyd[i,j]
對于限制k,點集的情況是:加了權最小的m個(0<=m<=N),這些點的權都不超過k
因此將點按權值升序排列.dist[k][i][j]表示:前k個點被加入后,i,j間的最短路.
代碼如下:
1
#include <iostream>
2using namespace std;
3int T,N,M,Q,pc[210];
4int C[210],dist[210][210][210];
5
bool mycmp(int a, int b)
{
6
return (C[a]<C[b]);
7
}
8int main(){
9 int i,j,k,p,a,b,c;
10 scanf("%d",&T);
11
while(T--){
12 memset(dist,0xff,sizeof(dist));
13 scanf("%d%d",&N,&M);
14 C[pc[0]=0]=-1;
15 for(i=1;i<=N;i++){
16 scanf("%d",&C[i]);
17 pc[i]=i;
18
}
19 sort(pc,pc+N+1,mycmp);
20 for(i=1; i<=M; i++){
21 scanf("%d%d%d",&a,&b,&c);
22 dist[0][a+1][b+1]=c;
23 dist[0][b+1][a+1]=c;
24 }
25 //floyd
26 for(k=1; k<=N; k++){
27 p=pc[k];
28 for(i=1; i<=N; i++){
29 for(j=1; j<=N; j++){
30 if(dist[k][i][j]<0)
31 dist[k][i][j]=dist[k-1][i][j];
32 else if(dist[k-1][i][j]>=0)
33 dist[k][i][j]=min(dist[k][i][j],dist[k-1][i][j]);
34
35 if(i!=j && dist[k-1][i][p]>=0 && dist[k-1][p][j]>=0){
36 if(dist[k][i][j]<0)
37 dist[k][i][j]=dist[k-1][i][p]+dist[k-1][p][j];
38 else
39 dist[k][i][j]=min(dist[k][i][j], dist[k-1][i][p]+dist[k-1][p][j]);
40 }
41 //printf("%d,%d,%d(%d) ",k,i,j,dist[k][i][j]);
42 }
43 }
44 }
45 //query
46 scanf("%d",&Q);
47 while(Q--){
48 scanf("%d%d%d",&a,&b,&c);
49 //順序查找
50 for(i=0; i<=N && C[pc[i]]<=c; i++);
51 printf("%d\n",dist[i-1][a+1][b+1]);
52 }
53 printf("\n");
54 }
55 return 0;
56}
57
posted on 2009-03-31 14:39
wolf5x 閱讀(253)
評論(0) 編輯 收藏 引用 所屬分類:
acm_icpc 、
algorithm