POJ 2502 Subway(最短路,自行建图)

Description

小k要从家去学校，他可以选择步行或者地铁，步行的速度是10km/h，地铁的速度是40km/h。(忽略等待地铁的时间)

小k可以随意上下地铁，并且可以(通过步行)在地铁线路之间转换。所有的地铁运行都是双向的。

求从家到校的最短用时。

Analyze

此题最重要的地方在于建模：构图。

将家设为点0，学校设为点1，每个地铁站(假设共有x个)站点都设为一点，相邻两个之间的边(地铁边)的权值是距离/地铁速度。将这(x+2)个点中任意两个之间建立步行边，权值是距离/步行速度。

Code

#include <cmath>
#include <string>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const double eps = 1e-8;
const double INF = double(0x3f3f3f3f);

typedef pair<double, double> P;
P node[505];
int cnt;
double e[220][220];

double dis(P a, P b)
{
    return sqrt( (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second) );
}

void floyd()
{
    for(int k = 0; k < cnt; ++k)
        for(int i = 0; i < cnt; ++i)
            for(int j = 0; j < cnt; ++j)
                if(e[i][j] > e[i][k] + e[k][j])
                    e[i][j] = e[i][k] + e[k][j];
}

void init()
{
    for(int i = 0; i < 210; ++i)
        for(int j = 0; j < 220; ++j)
            e[i][j] = e[j][i] = (i == j ? 0 : INF);
}

int main()
{
    init();
    double x, y;
    scanf("%lf %lf", &x, &y);
    node[cnt++] = P(x, y);///start : 0
    scanf("%lf %lf", &x, &y);
    node[cnt++] = P(x, y);///end : 1

    int pos = 2;
    while(~scanf("%lf%lf", &x, &y))
    {
        if(fabs(x + 1.0) < eps && fabs(y + 1.0) < eps)
        {
            for(int i = pos; i + 1 < cnt; ++i)
                e[i][i + 1] = e[i + 1][i] = dis(node[i], node[i + 1]) / 40000.0;
            pos = cnt;
        }
        else
            node[cnt++] = P(x, y);
    }
    for(int i = 0; i < cnt; ++i)
        for(int j = i + 1; j < cnt; ++j)
            e[i][j] = e[j][i] = min(e[i][j], dis(node[i], node[j]) / 10000.0);
    floyd();
    printf("%d", int(e[0][1] * 60.0 + 0.5));
    return 0;
}
Copy
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