Problem Solving►UVa

UVa 10034 - Freckles

Contents

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

Problem

題目網址
中文網址

找出相連所有點最短的路徑。

Solution

建好邊後，用 Prim’s Algorithm 即可。

Code

UVa 10034UVa 10034 - Freckles
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

#include<cstdio>
#include<cmath>
#include<climits>
#define N 101

struct Point
{
    double x, y;

    double getDistance(const Point& a)
    {
        return sqrt((x - a.x)*(x - a.x) + (y - a.y)*(y - a.y));
    }

}point[N];

double prim(int n);
int main()
{
    int Case;
    scanf("%d", &Case);

    int M[N][N] = {};
    while (Case--)
    {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%lf%lf", &point[i].x, &point[i].y);

        printf("%.2lf\n", prim(n));
        if (Case)
            putchar('\n');
    }

    return 0;
}
double prim(int n)
{
    bool isVisit[N] = {};
    double w[N][N] = {}, d[N];
    double sum = 0;

    //建 adjacency matrix
    int i, j;
    for (i = 0; i < n; i++)
        for (j = i + 1; j < n; j++)
            w[j][i] = w[i][j] = point[i].getDistance(point[j]);

    //從 0 開始走
    for (i = 0; i < n; i++)
        d[i] = w[0][i];
    isVisit[0] = true;

    for (i = 0; i < n; i++)
    {
        //找離樹最近的點
        int next = -1;
        double min = INT_MAX;
        for (j = 0; j < n; j++)
            if (d[j] < min&&!isVisit[j])
            {
            min = d[j];
            next = j;
            }

        //已經沒有離樹最近的點了
        if (next == -1)
            break;

        sum += min;
        isVisit[next] = true;

        //根據新加入的點，更新樹到各點的最短距離
        for (j = 0; j < n; j++)
            if (w[next][j] < d[j])
                d[j] = w[next][j];
    }

    return sum;
}