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; }