Problem Solving►UVa

UVa 11015 - 05-2 Rendezvous

Contents

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

Problem

中文網址

Solution

直接做 Floyd-Warshall ，再窮舉每個點來當見面點，求所要的 cost。

Code

UVa 11015
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
#include<cstdio>

int main()
{
    int n, m, Case = 1;
    char name[23][12];
    int d[23][23];
    while (scanf("%d%d", &n, &m) && n)
    {
        getchar();
        int i, j, k;
        for (i = 1; i <= n; i++)
            fgets(name[i], 12, stdin);

        int u, v, w;
        for (i = 1; i <= n; i++)
            for (j = 1; j <= n; j++)
                d[i][j] = 1e9;

        for (i = 1; i <= n; i++)
            d[i][i] = 0;

        for (i = 0; i < m; i++)
        {
            scanf("%d%d%d", &u, &v, &w);
            d[u][v] = d[v][u] = w;
        }


        for (k = 1; k <= n; k++)
            for (i = 1; i <= n; i++)
                for (j = 1; j <= n; j++)
                    if (d[i][k] + d[k][j] < d[i][j])
                        d[i][j] = d[i][k] + d[k][j];

        int min = 1e9, ans;
        for (i = 1; i <= n; i++)
        {
            int cost = 0;
            for (j = 1; j <= n; j++)
                cost += d[i][j];

            if (cost < min)
            {
                min = cost;
                ans = i;
            }
        }

        printf("Case #%d : %s", Case++, name[ans]);
    }

    return 0;
}