解題區/解題區 - UVa

UVa 11848 - Cargo Trains

contents

  1. 1. Problem
  2. 2. Sample input
  3. 3. Sample Output
  4. 4. Solution

Problem

在 N 個點的地圖中，有兩家運輸公司 A, B，如果它們都有在 x, y 之間部屬線路，則運輸費用將會根據參數 a 進行調整 a * Ca + (1 - a) * Cb，求從編號 0 到 N-1 的最少花費為何。

Sample input

1
2
3
4
5
6
7
8
9
3 2 2 3
0 1 100
1 2 200
0 1 200
1 2 150
0
1
0.5
-1 -1 -1 -1

Sample Output

1
2
3
350
300
325

Solution

每一次詢問 a 的時候，就做一次 spfa。似乎沒有別的方法可以預處理訊息。

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <stdio.h>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
int gA[128][128], gB[128][128];
int spfa(int st, int ed, int n, double p) {
    double dist[128];
    int inq[128] = {}, u, v;
    queue<int> Q;
    for(int i = 0; i < n; i++)
        dist[i] = 1e+10;
    dist[st] = 0, Q.push(st);
    while(!Q.empty()) {
        u = Q.front(), Q.pop();
        inq[u] = 0;
        for(int i = 0; i < n; i++) {
            int wa = gA[u][i], wb = gB[u][i];
            double cost = 0;
            if(wa < 0 && wb < 0)	continue;
            if(wa >= 0 && wb >= 0)
                cost = wa * p + wb * (1-p);
            else
                cost = wa >= 0 ? wa : wb;
            if(dist[i] > dist[u] + cost) {
                dist[i] = dist[u] + cost;
                if(!inq[i])
                    inq[i] = 1, Q.push(i);
            }
        }
    }
    return (int)dist[ed];
}
int main() {
    int N, Na, Nb, Q;
    int x, y, v;
    double p;
    while(scanf("%d %d %d %d", &N, &Na, &Nb, &Q) == 4 && N >= 0) {
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                gA[i][j] = gB[i][j] = -1;
        for(int i = 0; i < Na; i++) {
            scanf("%d %d %d", &x, &y, &v);
            if(gA[x][y] != -1)
                gA[x][y] = gA[y][x] = min(gA[x][y], v);
            else
                gA[x][y] = gA[y][x] = v;
        }
        for(int i = 0; i < Nb; i++) {
            scanf("%d %d %d", &x, &y, &v);
            if(gB[x][y] != -1)
                gB[x][y] = gB[y][x] = min(gB[x][y], v);
            else
                gB[x][y] = gB[y][x] = v;
        }
        for(int i = 0; i < Q; i++) {
            scanf("%lf", &p);
            printf("%d\n", spfa(0, N-1, N, p));
        }
    }
    return 0;
}