mayoko’s diary

プロコンとかいろいろ。

AOJ 1182 Railway Connection

解法

めんどくさいダイクストラみたいな感じです。

ダイクストラするとき, d[v][c] = (直前に乗った電車が c であって今いる頂点が v であるようなものの最短距離) というのが一番わかりやすそうですが, r_jk が単調減少であることを利用すると, v -> (路線 c を通る) -> u -> (路線 c を通る) -> w と考えて (v -> u での値段) + (u -> w での値段) の値段とやるよりも, (v -> w での値段) のほうが必ず安いので, d[v] = (頂点 v までの最短距離) とするだけで良いです。

const int MAXN = 111;
const int MAXC = 22;
const int MAXP = 55;
const int MAXD = 111*200;
const int INF = 1e9;

int d[MAXC][MAXN][MAXN];
ll value[MAXC][MAXD];
int p[MAXC], q[MAXC][MAXP], r[MAXC][MAXP];
int N, M, C, s, g;

struct edge {
    int v;
    ll w;
    edge() {}
    edge(int v, ll w) : v(v), w(w) {};
};

vector<ll> dijkstra(int n, vector<vector<edge> >& G, int s) {
    vector<ll> d(n, LLONG_MAX/10); d[s] = 0;
    priority_queue<pair<ll, int> > que;
    que.push(make_pair(0ll, s));
    while (!que.empty()) {
        auto p = que.top(); que.pop();
        int u = p.second;
        ll dist = -p.first;
        if (dist > d[u]) continue;
        for (edge e : G[u]) {
            if (d[e.v] > d[u]+e.w) {
                d[e.v] = d[u] + e.w;
                que.push(make_pair(-d[e.v], e.v));
            }
        }
    }
    return d;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (cin >> N >> M >> C >> s >> g) {
    	--s; --g;
    	if (N==0) break;
    	for (int c = 0; c < C; c++) {
    		for (int i = 0; i < N; i++) {
    			for (int j = 0; j < N; j++)
    				d[c][i][j] = INF;
    			d[c][i][i] = 0;
    		}
    	}
    	for (int i = 0; i < M; i++) {
    		int x, y, dist, c;
    		cin >> x >> y >> dist >> c;
    		--x; --y; --c;
    		d[c][x][y] = d[c][y][x] = min(dist, d[c][x][y]);
    	}
    	for (int c = 0; c < C; c++) {
    		for (int k = 0; k < N; k++) for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
    			d[c][i][j] = min(d[c][i][j], d[c][i][k] + d[c][k][j]);
    		}
    	}
    	for (int i = 0; i < C; i++)
    		cin >> p[i];
    	for (int i = 0; i < C; i++) {
    		for (int j = 1; j < p[i]; j++)
    			cin >> q[i][j];
    		q[i][p[i]] = MAXD-1;
    		for (int j = 1; j <= p[i]; j++)
    			cin >> r[i][j];
    		for (int k = 1; k <= p[i]; k++) {
    			for (int z = q[i][k-1]+1; z <= q[i][k]; z++) {
    				value[i][z] = value[i][z-1] + r[i][k];
    			}
    		}
    	}
    	vector<vector<edge> > G(N);
    	for (int v = 0; v < N; v++) for (int u = 0; u < N; u++) {
    		ll mini = INF;
    		for (int c = 0; c < C; c++) {
    			if (d[c][v][u] < MAXD)
    				mini = min(mini, value[c][d[c][v][u]]);
    		}
    		if (mini < INF) {
    			G[v].emplace_back(u, mini);
    			G[u].emplace_back(v, mini);
    		}
    	}
    	auto d = dijkstra(N, G, s);
    	ll ans = d[g];
    	if (ans > INF) ans = -1;
    	cout << ans << endl;
    }
    return 0;
}