Problem Solving►UVa

UVa 11792 - Krochanska is Here

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

Solution

雖然題目有提到「位在一個去其他地方都是最快的重點車站」，但似乎只要處理
「從他座落的重點車站到其他重點車站，行進時間的平均值會達到最小」就行了。

邊建圖時，一邊記下 重點車站，接著再以每個重點車站開始做 BFS 計算到每重點的距離即可。(找最小的)

Code

UVa 11792
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <cstdio>
#include <cstring>
#define N 10001
#define S 30000

struct node
{
    int v, next;
};
node edge[S];
int n, imp_size; //總車站數, 重點車站的數量
int adj[N];      //adjacent list
int used[N];     //計算重點車站
char str[10000];
inline int read()
{
    int n = 0;
    char ch;
    while ((ch = getchar()) >= '0' && ch <= '9')
        n = n * 10 + ch - '0';

    return n;
}
int BFS(int start)
{
    static int Q[N]; //queue
    int visited[N] = {};

    Q[0] = start;
    int qf = 0, qb = 1; //queue
    int times = 0;      //耗時，兩小時為一單位
    int count = 1;      //已到達的車站數
    visited[start] = 1; //方便判斷，每個都多 1

    while (qf < qb)
    {
        int now = Q[qf++];

        for (int i = adj[now]; i != -1; i = edge[i].next)
        {
            int v = edge[i].v;
            if (!visited[v])
            {
                visited[v] = visited[now] + 1;

                if (used[v] > 1) //important
                {
                    times += visited[v];
                    if (++count == imp_size)
                        return times;
                }

                Q[qb++] = v;
            }
        }
    }

    return 1e9;
}
int main()
{
    int T = read();    
    
    while (T--)
    {
        memset(adj, -1, sizeof adj);
        int imp[100]; // 重點車站
        int s, idx = 0;
        imp_size = 0;
        n = read();
        s = read();

        for (int i = 0; i < s; ++i)
        {
            int u = read(), v;
            ++used[u];
            while ((v = read()) != 0)
            {
                edge[idx] = (node){v, adj[u]}; //u -> v
                adj[u] = idx++;
                edge[idx] = (node){u, adj[v]}; //v -> u
                adj[v] = idx++;

                if (used[u = v] < 2)
                    ++used[u];
            }
        }

        for (int i = 1; i <= n; ++i)
            if (used[i] > 1)
                imp[imp_size++] = i;

        int min_time = 1e9, ans = 0;
        for (int i = 0; i < imp_size; ++i)
        {
            int sum = BFS(imp[i]);
            if (sum < min_time)
            {
                min_time = sum;
                ans = imp[i];
            }
            else if (sum == min_time && imp[i] < ans)
                ans = imp[i];
        }

        printf("Krochanska is in: %d\n", ans);
        memset(used, 0, sizeof used);
    }

    return 0;
}