Algoogle

Algorithm for Programming Contest

AOJ 1182 Railway Connection

Category: AOJ Tag: warshall-floyd

Railway Connection

問題概要


駅と駅を繋ぐ路線には鉄道会社と距離が決まっている.
各鉄道会社の距離に応じた運賃の計算方法が与えられるとき, 駅sから駅gまでの最小の運賃を求めよ.

解法


鉄道会社ごとにwarshall-floydで駅から駅までの最短距離を求めておく.
距離は高々20000なのでこれも予め鉄道会社ごとに距離に対する運賃を求めておく.
あとは各駅間の最小の運賃をwarshall-floydで求めればよい.

コード


(1182.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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a) for(int i = 0; i < (int)(a); i++)
const int inf = 1e9;

int N, M, C, s, g;
int dist[32][128][128], p[32], q[32][64], r[32][64];
int fare[32][20010], cst[128][128];

int solve(){
    rep(c,C)rep(k,N)rep(i,N)rep(j,N)
        dist[c][i][j] = min(dist[c][i][j], dist[c][i][k]+dist[c][k][j]);
    rep(c,C){
        int cur = 0; fare[c][0] = 0;
        rep(i,20000){
            if(cur < p[c]-1 and i == q[c][cur]) cur++;
            fare[c][i+1] = fare[c][i] + r[c][cur];
        }
    }
    rep(i,N)rep(j,N) cst[i][j] = inf;
    rep(c,C)rep(i,N)rep(j,N) if(dist[c][i][j] < inf) cst[i][j] = min(cst[i][j], fare[c][dist[c][i][j]]);
    rep(k,N)rep(i,N)rep(j,N) cst[i][j] = min(cst[i][j], cst[i][k]+cst[k][j]);
    return cst[s][g]==inf? -1: cst[s][g];
}

bool input(){
    cin >> N >> M >> C >> s >> g;
    s--; g--;
    rep(c,C)rep(i,N)rep(j,N) dist[c][i][j] = inf;
    rep(i,M){
        int x, y, d, c;
        cin >> x >> y >> d >> c;
        x--; y--; c--;
        dist[c][x][y] = dist[c][y][x] = min(dist[c][x][y], d);
    }
    rep(c,C) cin >> p[c];
    rep(c,C) {
        rep(i,p[c]-1) cin >> q[c][i];
        rep(i,p[c]) cin >> r[c][i];
    }
    return N;
}

int main(){
    while(input()) cout << solve() << endl;
    return 0;
}

Comments