最近做了兩道floyd變種的題目,又加深了對(duì)floyd原理的理解.

第2題: tju 3214 Find the Path
http://acm.tju.edu.cn/toj/showp3214.html

題目大意是給一個(gè)無向圖,每個(gè)結(jié)點(diǎn)有個(gè)點(diǎn)權(quán)c[p]
對(duì)于查詢的點(diǎn)對(duì)i,j和權(quán)k,求在中間節(jié)點(diǎn)(不包含端點(diǎn)i,j)權(quán)值不大于k的限制下,i,j間最短路徑.
由于查詢次數(shù)多,因此一次查詢復(fù)雜度需要在O(logn)以內(nèi).考慮計(jì)算出所有點(diǎn)對(duì)在所有限制條件下的最短路,O(1)查詢.
限制條件不作用于端點(diǎn)i,j,正好可以用floyd解決.因?yàn)閒loyd正是不斷向中間點(diǎn)集中加入點(diǎn).只要限制一下這些被加入點(diǎn)的條件,就可以解決這題了.
初步歸納,對(duì)于查詢i,j,k,應(yīng)該輸出將所有c[p]<=k的點(diǎn)加入后的floyd[i,j]
對(duì)于限制k,點(diǎn)集的情況是:加了權(quán)最小的m個(gè)(0<=m<=N),這些點(diǎn)的權(quán)都不超過k
因此將點(diǎn)按權(quán)值升序排列.dist[k][i][j]表示:前k個(gè)點(diǎn)被加入后,i,j間的最短路.

代碼如下:
 

 1#include <iostream>
 2using namespace std;
 3int T,N,M,Q,pc[210];
 4int C[210],dist[210][210][210]; 
 5bool 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