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]);
}
}
沒有留言:
張貼留言