2005-Water Pipe Construction

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2005&lang=jp
パイプは両方向に対して建築が可能だと思いこんでいて何度もWAを出してしまった。

考え方
中継点iから2つの路線に分岐したと考える。
すると、求める解ansは、全点対最短距離をGで表わすと
ans=min(ans,G[s][i]+G[i][g1]+G[i][g2]);
となる。

実装(C++)

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <ctime>
#include <cassert>
#include <cwchar>
#include <cstdarg>
#include <cwctype>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <functional>
#include <iomanip>

using namespace std;
typedef long long int lli;
typedef unsigned int uint;

typedef int Weight;
const Weight INF=49999999;
typedef vector<vector<Weight> > Matrix;

void warshall_floyd(Matrix& G){
	int V=G.size();
	for(int k=0;k<V;k++)
		for(int i=0;i<V;i++)
			for(int j=0;j<V;j++)
				G[i][j]=min(G[i][j],G[i][k]+G[k][j]);
}

int main(){
	int n,s,g1,g2,m,a,b,c;
	for(;;){
		scanf("%d%d%d%d%d",&n,&m,&s,&g1,&g2);s--;g1--;g2--;
		if(n==0)break;
		Matrix G(n);
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				G[i].push_back(i!=j?INF:0);
			}
		}
		for(int i=0;i<m;i++){
			scanf("%d%d%d",&a,&b,&c);
			a--;b--;G[a][b]=c;
		}
		warshall_floyd(G);
		int res=INF;
		for(int i=0;i<n;i++){
			res=min(res,G[s][i]+G[i][g1]+G[i][g2]);
		}
		printf("%d\n",res);
		fflush(stdout);
	}
	return 0;
}