Problem 2005 : Water Pipe Construction

Problem 2005 : Water Pipe Construction
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2005

• 問題概要

ひとつの水源と基地がいくつかあたえられる。道でつながっていて、
そこに水路をつくるためにかかるコストが与えられる。
特定の二つの基地と水源を結ぶ水路をつくるとき、もっとも低いコストを答えよ。
ただし、そのコストはその与えられた向きのみで有効である。

• 解法

ワーシャルフロイドで全点間の距離をだす。
そして、ノードをひとつづつ注目していき、水源からそのノードの水路、
そのノードから目的地の基地二つへの水路をつくるコストの合計が最小のものが答え。

• ソース

#include<iostream>
#include<algorithm>

#define INF 10000000

using namespace std;

main(){

  int node, edge, source, dst1, dst2;
  
  while(cin >> node >> edge >> source >> dst1 >> dst2){
    if(node == 0)break;
    source--;
    dst1--;
    dst2--;
    
    int d[node][node];
    fill(&d[0][0], &d[node-1][node], INF);

    for(int i=0; i<node; i++){
      d[i][i] = 0;
    }

    for(int i=0; i<edge; i++){
      int f, t;
      cin >> f >> t;
      cin >> d[f-1][t-1];
    }

    for(int i=0; i<node; i++){
      for(int j=0; j<node; j++){
	for(int k=0; k<node; k++){
	  d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
	}
      }
    }

    int ans = INF;

    for(int i=0; i<node; i++){
      ans = min(ans, d[source][i] + d[i][dst1] + d[i][dst2]);
    }

    cout << ans << endl;
  }
}