AOJ 2005: Water Pipe Construction

アルゴリズム

そすうライブラリのverifyに使われていたので解いてみた。

問題

Water Pipe Construction | Aizu Online Judge

  • 有向グラフと各辺のコストが与えられる。
  • 頂点sから頂点g1とg2を結ぶコスト最小の道を作るときのコストを求めよ

解法

全点対間の最小コストを求めておいて、全ての頂点vについて「sからvの最小コスト」+「vからg1の最小コスト」+「vからg2の最小コスト」を調べて最小となるコストを返せばよい。

ダイクストラ

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

struct edge {
    int src, dst, cost; 
    edge(int s, int t, int c): src(s), dst(t), cost(c) {}
};
const int INF = 1e8;

void dijkstra(const vector<vector<edge> > &G, vector<int> &d, const int s) {
    d.assign(d.size(), INF);
    d[s] = 0;
    typedef pair<int, int> P;
    priority_queue<P, vector<P>, greater<P> > que;
    que.push(P(0, s));

    while(!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second;
        if(d[v] < p.first) continue;
        for(auto &e : G[v]) {
            if(d[e.dst] > d[v] + e.cost) {
                d[e.dst] = d[v] + e.cost;
                que.push(P(d[e.dst], e.dst));
            }
        }
    }
}

int main(void) {
    int n, m, s, g1, g2;
    while(cin >> n >> m >> s >> g1 >> g2 && n) {
        vector<vector<edge> > G(n);
        vector<vector<int> > d(n, vector<int>(n));
        --s; --g1; --g2;
        REP(i, m) {
            int b1, b2, c;
            cin >> b1 >> b2 >> c;
            G[b1-1].push_back(edge(b1-1, b2-1, c));
        }
        REP(i, n) {
            dijkstra(G, d[i], i);
        }
        int cost = numeric_limits<int>::max();
        REP(i, n) {
            cost = min(cost, d[s][i] + d[i][g1] + d[i][g2]);
        }
        cout << cost << endl;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2098833

ベルマン・フォード

#include <bits/stdc++.h>
  
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
struct edge {
    int src, dst, cost; 
    edge(int s, int t, int c): src(s), dst(t), cost(c) {}
};
 
const int INF = 1e8;
 
void bellman_ford(const vector<edge> &edges, vector<int> &d, const int s) {
    d.assign(d.size(), INF);
    d[s] = 0;
    for(auto &i : d) {
        for(auto &e : edges) {
            d[e.dst] = min(d[e.dst], d[e.src] + e.cost);
        }
    }
}
 
int main(void) {
    int n, m, s, g1, g2;
    while(cin >> n >> m >> s >> g1 >> g2 && n) {
        vector<edge> edges;
        vector<vector<int> > d(n, vector<int>(n));
        --s; --g1; --g2;
        REP(i, m) {
            int b1, b2, c;
            cin >> b1 >> b2 >> c;
            edges.push_back(edge(b1-1, b2-1, c));
        }
        REP(i, n) {
            bellman_ford(edges, d[i], i);
        }
        int cost = numeric_limits<int>::max();
        REP(i, n) {
            cost = min(cost, d[s][i] + d[i][g1] + d[i][g2]);
        }
        cout << cost << endl;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2098843

ベルマン・フォードは次のような実装でもよい。

void bellman_ford(const vector<edge> &edges, vector<int> &d, const int s) {
    d.assign(d.size(), INF);
    d[s] = 0;
    for(int i=0; i < edges.size(); ++i) {
        edge e = edges[i];
        if (d[e.dst] > d[e.src] + e.cost) {
            d[e.dst] = d[e.src] + e.cost;
            i = -1;
        }
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2098773

ワーシャル・フロイド

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

struct edge {
    int src, dst, cost; 
    edge(int s, int t, int c): src(s), dst(t), cost(c) {}
};
const int INF = 1e8;

void warshall_floyd(vector<vector<int> > &d, vector<edge> &edges) {
    for(size_t i=0; i<d.size(); ++i) {
        d[i].assign(d[i].size(), INF);
        d[i][i] = 0;
    }
    for(auto &e : edges) {
        d[e.src][e.dst] = e.cost;
    }
    const size_t n = d.size();
    for(size_t j=0; j<n; ++j) {
        for(size_t i=0; i<n; ++i) {
            for(size_t k=0; k<n; ++k) {
                d[i][k] = min(d[i][k], d[i][j] + d[j][k]);
            }
        }
    }
}

int main(void) {
    int n, m, s, g1, g2;
    while(cin >> n >> m >> s >> g1 >> g2 && n) {
        vector<edge> edges;
        vector<vector<int> > d(n, vector<int>(n, INF));
        --s; --g1; --g2;
        REP(i, m) {
            int b1, b2, c;
            cin >> b1 >> b2 >> c;
            edges.push_back(edge(b1-1, b2-1, c));
        }
        warshall_floyd(d, edges);
        int cost = numeric_limits<int>::max();
        REP(i, n) {
            cost = min(cost, d[s][i] + d[i][g1] + d[i][g2]);
        }
        cout << cost << endl;
    }
 }

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2098872

追記: 添字の順番を間違えたワーシャル・フロイド

qiita.com

KIJ （正しい）

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

AC: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3455812

KJI （KIJと同じはず）

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

AC: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3455808

IJK

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

WA: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3455813

IJK x 3

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

AC: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3455814

IKJ x 3

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

AC: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3455815

JIK x 3

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

AC: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3455817

JKI x 3

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

AC: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3455819