UVa 10354 Problem B - Avoiding Your Boss [Graph]

7760819      10354      Avoiding Your Boss      poao899      Accepted      C++      0.040      2010-02-17 13:09:02                                               .


唔  簡單來說

一張無向有權圖

找到TH <-> M 的最短路徑

但不能經過BH <-> OF任何一條最短路徑的任一節點







反正會在最短路徑上的點就表示dist[bh][i]+dist[i][of] = dist[bh][of]嘛ˇ







#include<stdio.h>
#define MAX 1000000000

int dist[110][110],d2[110][110];
int p,r,bh,of,th,m,p1,p2,d,ti,tj,tk;
bool can[110];

main(){
    while(~scanf("%d%d%d%d%d%d",&p,&r,&bh,&of,&th,&m)){
        //Init
        for(int i=0;i<110;i++){
            for(int j=0;j<110;j++){
                dist[i][j]=d2[i][j]=MAX;
            }
            dist[i][i]=d2[i][i]=0;
            can[i]=1;
        }

        //Input E
        while(r--){
            scanf("%d%d%d",&p1,&p2,&d);
            dist[p1][p2]=d2[p1][p2]=dist[p2][p1]=d2[p2][p1]=d;
        }

        //First Warshall : Find BH <-> OF

        for(int k=0;k<=p;k++)
            for(int i=0;i<=p;i++)
                for(int j=0;j<=p;j++)
                    if(dist[i][k]+dist[k][j] < dist[i][j])
                        dist[i][j]=dist[i][k]+dist[k][j];

            //Find Nodes Which Would Be Visited By Boss

        for(int i=0;i<=p;i++)
            if(dist[bh][i]+dist[i][of] == dist[bh][of])
                can[i]=0;


        //Second Warshall : Find TH <-> M

        for(int k=0;k<=p;k++)
            if(can[k])
                for(int i=0;i<=p;i++)
                    if(can[i])
                        for(int j=0;j<=p;j++)
                            if(can[j])
                                if(d2[i][k]+d2[k][j] < d2[i][j])
                                    d2[i][j]=d2[i][k]+d2[k][j];

        //Output

        if(d2[th][m]==MAX || !can[th] || !can[m])
            puts("MISSION IMPOSSIBLE.");
        else printf("%d\n",d2[th][m]);
    }
}