解題區/解題區 - UVa

UVa 1000 - Airport Configuration

contents

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

Problem

機場有一個長形走廊，其中南側是搭機處，北側是下機處。

給予很多城市間旅客的數量，從城市 A 到城市 B 的旅客 X 人會在這個機場上進行轉換。

現在讀入機場的放置口設定 (順序)，請問每一種設定所產生的負載為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
3
1  2  2 10  3 15
2  1  3 10
3  2  1 12  2 20
1
1 2 3
2 3 1
2
2 3 1
3 2 1
0
2
1  1  2 100
2  1  1 200
1
1 2
1 2
2
1 2
2 1
0
0

Sample Output

1
2
3
4
5
6
Configuration Load
    2         119
    1         122
Configuration Load
    2         300
    1         600

Solution

沒有要求最佳化，模擬即可。

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
#include <stdio.h> 
#include <algorithm>
#include <vector>
#include <stdlib.h>
using namespace std;
int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
        int A[32][32] = {}, x, city_id, dest, k;
        int north[32], south[32];
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &city_id, &k);
            for (int j = 0; j < k; j++) {
                scanf("%d %d", &dest, &x);
                A[city_id][dest] += x;
            }
        }
        vector< pair<int, int> > ret;
        for (; scanf("%d", &city_id) == 1 && city_id;) {
            for (int i = 0; i < n; i++)
                scanf("%d", &north[i]);
            for (int i = 0; i < n; i++)
                scanf("%d", &south[i]);
            int load = 0;
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    load += A[north[i]][south[j]] * (abs(i - j) + 1);
            ret.push_back(make_pair(load, city_id));
        }
        sort(ret.begin(), ret.end());
        puts("Configuration Load");
        for (int i = 0; i < ret.size(); i++) {
            printf("%5d         %d\n", ret[i].second, ret[i].first);
        }
    }
    return 0;
}