Algoogle

Algorithm for Programming Contest

AOJ 2005 Water Pipe Construction

Category: AOJ Tag: warshall-floyd

Water Pipe Construction

問題概要


解法


ワーシャルフロイドで全点対最短路を求めておいて, 枝分かれする場所を選ぶ.

コード


(2005.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define rep(i,a) for(int i = 0;i < (a); i++)
#define INF 1e8
typedef vector<int> vi;

int main(){
    int n, m, s, g1, g2;
    while(cin >> n >> m >> s >> g1 >> g2, n||m||s||g1||g2){
        s--; g1--; g2--;
        vector<vi> c(n,vi(n,INF));
        rep(i,m){
            int b1, b2, c1;
            cin >> b1 >> b2 >> c1;
            c[--b1][--b2] = c1;
        }
        rep(i,n) c[i][i] = 0;
        rep(k,n) rep(i,n) rep(j,n){
            c[i][j] = min(c[i][j], c[i][k]+c[k][j]);
        }
        int ans = INF;
        rep(i,n){
            ans = min(ans, c[s][i] + c[i][g1] + c[i][g2]);
        }
        cout << ans << endl;
    }
}

Comments