AOJ 2005 Water Pipe Construction
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2005
#include <cstdio> #include <algorithm> using namespace std; const int INF = 1<<29; const int MAX_N = 100; int N,M,S,G0,G1; int cost[MAX_N][MAX_N]; int min_cost[MAX_N][MAX_N]; int wf(){ for(int k=0; k<N; k++)for(int i=0; i<N; i++)for(int j=0; j<N; j++){ min_cost[i][j] = min(min_cost[i][j], min_cost[i][k] + min_cost[k][j]); if(min_cost[i][j] > INF) min_cost[i][j] = INF; } } int main(){ while(scanf("%d %d %d %d %d",&N,&M,&S,&G0,&G1) && N!=0){ S--; G0--; G1--; for(int i=0;i<N;i++)for(int j=0;j<N;j++) min_cost[i][j] = cost[i][j] = (i==j)?0:INF; for(int i=0;i<M;i++){ int v, u, c; scanf("%d %d %d",&v,&u,&c); v--; u--; min_cost[v][u] = cost[v][u] = c; } wf(); int ans=INF; for(int k=0;k<N;k++) ans = min(ans, min_cost[S][k]+min_cost[k][G0]+min_cost[k][G1]); printf("%d\n", ans); } }