POJ ~ 2502 ~ Subway （Dijkstra + 建图）

季俭

2023-12-01

题意：你要从家去学校，先输入你家和学校的坐标。有一些地铁站线，每一条线上有一些站点，每一条线以一对-1，-1结束，地铁站的输入以EOF结束。坐标单位为米，你行走速度为10km/h，地铁速度为40km/h，问你最快多少分钟可以到学校？

地铁只能一站一站的走，方向随意，不能从1号站点跳到3号站点，也不能从第一条线上的站点到另一条线上的站点。

思路：一看就是Dijkstra，主要是建图稍微比较麻烦，而且权值不是路程，而是时间，因为要求的时间最短，而不是路程最短。我们可以先把所有站点，家和学校，他们的坐标和几号线（家设置为0，学校设置为1，其他的依次往后增加）都存到一个vector里面。然后双重for遍历vector，处理之间需要花费的时间。同一条线的站点且是相邻的站点的时间为距离/地铁速度，其他的都为距离/步行速度。

wa的小朋友看这里：也许两个不相邻的站点间，坐车过去还没有走着快呢。

数据网址：B题

防止网址过期，下面贴几份数据。

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<cstring>
using namespace std;
const int MAXN = 1e6 + 5;
const int INF = 0x3f3f3f3f;
struct Edge
{
    int from, to/*, dist*/;       //起点,终点,距离
    double dist;
    //Edge(int u, int v, int w):from(u), to(v), dist(w) {}
    Edge(int u, int v, double w):from(u), to(v), dist(w) {}
};

struct Dijkstra
{
    int n, m;                 //结点数,边数(包括反向弧)
    vector<Edge> edges;       //边表。edges[e]和edges[e^1]互为反向弧
    vector<int> G[MAXN];      //邻接表，G[i][j]表示结点i的第j条边在edges数组中的序号
    int vis[MAXN];            //标记数组
    //int d[MAXN];              //s到各个点的最短路
    double d[MAXN];
    int pre[MAXN];            //上一条弧

    void init(int n)
    {
        this->n = n;
        edges.clear();
        for (int i = 0; i <= n; i++) G[i].clear();
    }

    //void add_edge(int from, int to, int dist)
    void add_edge(int from, int to, double dist)
    {
        edges.push_back(Edge(from, to, dist));
        m = edges.size();
        G[from].push_back(m - 1);
    }

    struct HeapNode
    {
        int from/*, dist*/;
        double dist;
        bool operator < (const HeapNode& rhs) const
        {
            return rhs.dist < dist;
        }
        //HeapNode(int u, int w): from(u), dist(w) {}
        HeapNode(int u, double w): from(u), dist(w) {}
    };

    void dijkstra(int s)
    {
        priority_queue<HeapNode> Q;
        for (int i = 0; i <= n; i++) d[i] = INF;
        d[s] = 0;
        memset(vis, 0, sizeof(vis));
        Q.push(HeapNode(s, 0));
        //Q.push((HeapNode){s, 0});    G++编译通过，C++可能会编译错误
        while (!Q.empty())
        {
            HeapNode x = Q.top(); Q.pop();
            int u = x.from;
            if (vis[u]) continue;
            vis[u] = true;
            for (int i = 0; i < G[u].size(); i++)
            {
                Edge& e = edges[G[u][i]];
                if (d[e.to] > d[u] + e.dist)
                {
                    d[e.to] = d[u] + e.dist;
                    pre[e.to] = G[u][i];
                    Q.push(HeapNode(e.to, d[e.to]));
                    //Q.push((HeapNode){e.to, d[e.to]});     G++编译通过，C++可能会编译错误
                }
            }
        }
    }
};
Dijkstra solve;
const double v1 = 10000.0 / 60.0;
const double v2 = 40000.0 / 60.0;
struct Point
{
    int x, y, line;
    Point(int a, int b, int c): x(a), y(b), line(c) {}
};
vector<Point> v;
double Distance(int a, int b)
{
    return sqrt(pow(v[a].x - v[b].x, 2) + pow(v[a].y - v[b].y, 2));
}
int main()
{
    int sx, sy, ex, ey;
    while (~scanf("%d%d%d%d", &sx, &sy, &ex, &ey))
    {
        v.clear();
        v.push_back(Point(sx, sy, 0));
        v.push_back(Point(ex, ey, 1));
        int x, y, line = 2;
        while (~scanf("%d%d", &x, &y))
        {
            v.push_back(Point(x, y, line));
            while (~scanf("%d%d", &x, &y) && !(x == -1 && y == -1))
            {
                v.push_back(Point(x, y, line));
            }
            line++;
        }
        solve.init(v.size());
        for (int i = 0; i < v.size(); i++)
        {
            for (int j = 0; j < v.size(); j++)
            {
                if (v[i].line == v[j].line && abs(i - j) == 1) solve.add_edge(i, j, Distance(i, j) / v2);
                else solve.add_edge(i, j, Distance(i, j) / v1);
            }
        }
        solve.dijkstra(0);
        printf("%.0f\n", solve.d[1]);
    }
    return 0;
}
/*
0 0 10000 1000
0 200 5000 200 7000 200 -1 -1
2000 600 5000 600 10000 600 -1 -1
*/

数据来了！！！！！！开心吗，宝贝。

1.in：

1 1 10001 10001
2777 886 7793 6915 5386 8335 6649 492 2362 1421 8690 27 7763 59 540 3926 9172 3426 5211 5736 2567 5368 5782 6429 2862 1530 4067 5123 3929 3135 4022 9802 3069 3058 1393 8167 5011 8456 6229 8042 4421 7373 3784 4919 5198 8537 8315 4324 6413 4370 6091 3526 9956 8980 6862 1873 6996 9170 2305 7281 7084 925 336 6327 846 6505 1313 1729 6124 5857 9582 3895 8814 545 5434 3367 4043 364 1087 3750 7276 6808 5788 7178 5403 3584 2754 2651 9932 2399 9676 5060 7739 3368 6226 12 8094 8586 795 7539 1434 570 7467 378 97 6601 3317 2902 6652 492 7301 756 4286 280 3865 9441 8444 9689 8440 6619 8031 4729 8097 8117 4481 5771 709 675 4567 8927 9497 7856 4586 2353 5306 6965 6219 4683 1528 8624 5732 2871 9503 8829 8270 19 9708 3368 6340 6715 7796 8149 2618 723 2846 2245 2921 3451 2379 3555 7764 7488 9841 8228 5193 2350 7034 1500 124 7764 6987 4914 3743 5856 2227 6491 9859 8365 1432 1936 6437 2551 3275 9228 1474 5407 8858 6121 6029 4395 8235 1237 5818 3793 6143 4428 5928 1011 8776 9529 4443 2404 4613 5763 8606 4538 2904 6840 5128 4818 7369 688 9917 7917 3324 6996 9470 7743 8490 2183 9772 5499 5644 6725 7505 5590 2954 8139 7669 9786 8542 8082 197 8464 9355 9507 6348 8804 3622 8611 9299 7828 5746 7343 4340 5568 3311 5422 7605 3810 5661 1801 4878 3730 9320 1305 9444 8736 8522 8626 6708 3465 8282 3416 2924 3258 2062 7637 2600 5624 3452 2036 9379 1899 7468 5550 973 71 3881 7131 8933 4930 8660 5894 7199 163 8899 7981 2959 2996 2813 3773 7190 9668 2926 1095 5084 6466 2090 1340 3376 7684 5936 5542 7445 9107 9179 9756 6887 8418 3348 9412 1659 2172 2336 2009 6342 5210 8206 7587 7713 9301 5321 7372 4819 1255 7721 4599 5939 9904 -1 -1
5667 3940 6228 1705 9150 1127 6658 5984 9224 3920 7269 2422 4081 1396 84 5630 1972 9292 3850 7672 5385 7625 9299 1222 6042 6640 713 3898 6190 2298 -1 -1
8209 2590 8819 8581 7732 9336 5994 1155 -1 -1
4769 379 1776 5273 7255 8850 8142 1860 5884 5579 3205 1993 -1 -1
2504 9567 1961 613 1326 2754 8944 4259 3202 8202 6784 3506 2842 2021 -1 -1
5189 9528 9908 8872 -1 -1

1.out：

2.in：

1 1 10001 10001
886 893 6915 6918 8335 8341 492 501 1421 1423 27 27 59 62 3926 3926 3426 3428 5736 5737 5368 5375 6429 6431 1530 1532 5123 5130 3135 3144 9802 9804 3058 3067 8167 8170 8456 8457 8042 8051 7373 7374 4919 4923 8537 8545 4324 4329 4370 4373 3526 3527 8980 8986 1873 1875 9170 9176 7281 7286 925 929 6327 6333 6505 6511 1729 1732 5857 5861 3895 3897 545 549 3367 3371 364 367 3750 3757 6808 6814 7178 7186 3584 3587 2651 2655 2399 2401 5060 5066 3368 3377 12 18 8586 8590 7539 7544 570 574 378 385 6601 6608 2902 2909 492 494 756 757 280 286 9441 9446 9689 9693 6619 6619 4729 4730 8117 8124 5771 5772 675 684 8927 8934 7856 7863 2353 2359 6965 6971 4683 4692 8624 8632 2871 2873 8829 8832 19 19 3368 3376 6715 6715 8149 8155 723 731 2245 2251 3451 3452 3555 3564 7488 7492 8228 8229 2350 2353 1500 1504 7764 7768 4914 4921 5856 5859 6491 6498 8365 8374 1936 1938 2551 2558 9228 9233 5407 5411 6121 6129 4395 4404 1237 1242 3793 3801 4428 4431 1011 1019 9529 9535 2404 2407 5763 5766 4538 4544 6840 6844 4818 4826 688 697 7917 7924 6996 7000 7743 7743 2183 2183 5499 5501 6725 6729 5590 5595 8139 8143 9786 9795 8082 8084 8464 8471 9507 9512 8804 8812 8611 8613 7828 7837 7343 7349 5568 5568 5422 5423 3810 3815 1801 1802 3730 3738 1305 1305 8736 8740 8626 8628 3465 3473 3416 3418 3258 3262 7637 7639 5624 5624 2036 2038 1899 1908 5550 5558 71 74 7131 7132 4930 4933 5894 5894 163 172 7981 7990 2996 3005 3773 3776 9668 9668 1095 1101 6466 6470 1340 1340 7684 7690 5542 5548 9107 9112 9756 9765 8418 8425 9412 9420 2172 2181 2009 2015 5210 5212 7587 7593 9301 9304 7372 7373 1255 1264 4599 4600 9904 9913 -1 -1
3940 3947 1705 1713 1127 1127 5984 5992 3920 3924 2422 2431 1396 1397 5630 5634 9292 9294 7672 7672 7625 7630 1222 1231 6640 6642 3898 3901 2298 2298 -1 -1
2590 2599 8581 8590 9336 9338 1155 1159 -1 -1
379 388 5273 5279 8850 8855 1860 1862 5579 5583 1993 1998 -1 -1
9567 9571 613 614 2754 2760 4259 4263 8202 8204 3506 3510 2021 2023 -1 -1
9528 9537 8872 8880 -1 -1

2.out：

3.in：

1 1 10001 10001
886 886 2777 2777 6915 6915 7793 7793 8335 8335 5386 5386 492 492 6649 6649 1421 1421 2362 2362 27 27 8690 8690 59 59 7763 7763 3926 3926 540 540 3426 3426 9172 9172 5736 5736 5211 5211 5368 5368 2567 2567 6429 6429 5782 5782 1530 1530 2862 2862 5123 5123 4067 4067 3135 3135 3929 3929 9802 9802 4022 4022 3058 3058 3069 3069 8167 8167 1393 1393 8456 8456 5011 5011 8042 8042 6229 6229 7373 7373 4421 4421 4919 4919 3784 3784 8537 8537 5198 5198 4324 4324 8315 8315 4370 4370 6413 6413 3526 3526 6091 6091 8980 8980 9956 9956 1873 1873 6862 6862 9170 9170 6996 6996 7281 7281 2305 2305 925 925 7084 7084 6327 6327 336 336 6505 6505 846 846 1729 1729 1313 1313 5857 5857 6124 6124 3895 3895 9582 9582 545 545 8814 8814 3367 3367 5434 5434 364 364 4043 4043 3750 3750 1087 1087 6808 6808 7276 7276 7178 7178 5788 5788 3584 3584 5403 5403 2651 2651 2754 2754 2399 2399 9932 9932 5060 5060 9676 9676 3368 3368 7739 7739 12 12 6226 6226 8586 8586 8094 8094 7539 7539 795 795 570 570 1434 1434 378 378 7467 7467 6601 6601 97 97 2902 2902 3317 3317 492 492 6652 6652 756 756 7301 7301 280 280 4286 4286 9441 9441 3865 3865 9689 9689 8444 8444 6619 6619 8440 8440 4729 4729 8031 8031 8117 8117 8097 8097 5771 5771 4481 4481 675 675 709 709 8927 8927 4567 4567 7856 7856 9497 9497 2353 2353 4586 4586 6965 6965 5306 5306 4683 4683 6219 6219 8624 8624 1528 1528 2871 2871 5732 5732 8829 8829 9503 9503 19 19 8270 8270 3368 3368 9708 9708 6715 6715 6340 6340 8149 8149 7796 7796 723 723 2618 2618 2245 2245 2846 2846 3451 3451 2921 2921 3555 3555 2379 2379 7488 7488 7764 7764 8228 8228 9841 9841 2350 2350 -1 -1
1500 1500 7034 7034 7764 7764 124 124 4914 4914 6987 6987 5856 5856 3743 3743 6491 6491 2227 2227 8365 8365 9859 9859 1936 1936 1432 1432 2551 2551 6437 6437 9228 9228 3275 3275 5407 5407 1474 1474 6121 6121 8858 8858 4395 4395 6029 6029 1237 1237 8235 8235 3793 3793 5818 5818 4428 4428 6143 6143 1011 1011 5928 5928 9529 9529 8776 8776 2404 2404 -1 -1

3.out：

4.in：

1 1 10001 10001
9383 9383 886 886 -1 -1
2777 2777 6915 6915 -1 -1
7793 7793 8335 8335 -1 -1
5386 5386 492 492 -1 -1
6649 6649 1421 1421 -1 -1
2362 2362 27 27 -1 -1
8690 8690 59 59 -1 -1
7763 7763 3926 3926 -1 -1
540 540 3426 3426 -1 -1
9172 9172 5736 5736 -1 -1
5211 5211 5368 5368 -1 -1
2567 2567 6429 6429 -1 -1
5782 5782 1530 1530 -1 -1
2862 2862 5123 5123 -1 -1
4067 4067 3135 3135 -1 -1
3929 3929 9802 9802 -1 -1
4022 4022 3058 3058 -1 -1
3069 3069 8167 8167 -1 -1
1393 1393 8456 8456 -1 -1
5011 5011 8042 8042 -1 -1
6229 6229 7373 7373 -1 -1
4421 4421 4919 4919 -1 -1
3784 3784 8537 8537 -1 -1
5198 5198 4324 4324 -1 -1
8315 8315 4370 4370 -1 -1
6413 6413 3526 3526 -1 -1
6091 6091 8980 8980 -1 -1
9956 9956 1873 1873 -1 -1
6862 6862 9170 9170 -1 -1
6996 6996 7281 7281 -1 -1
2305 2305 925 925 -1 -1
7084 7084 6327 6327 -1 -1
336 336 6505 6505 -1 -1
846 846 1729 1729 -1 -1
1313 1313 5857 5857 -1 -1
6124 6124 3895 3895 -1 -1
9582 9582 545 545 -1 -1
8814 8814 3367 3367 -1 -1
5434 5434 364 364 -1 -1
4043 4043 3750 3750 -1 -1
1087 1087 6808 6808 -1 -1
7276 7276 7178 7178 -1 -1
5788 5788 3584 3584 -1 -1
5403 5403 2651 2651 -1 -1
2754 2754 2399 2399 -1 -1
9932 9932 5060 5060 -1 -1
9676 9676 3368 3368 -1 -1
7739 7739 12 12 -1 -1
6226 6226 8586 8586 -1 -1
8094 8094 7539 7539 -1 -1
795 795 570 570 -1 -1
1434 1434 378 378 -1 -1
7467 7467 6601 6601 -1 -1
97 97 2902 2902 -1 -1
3317 3317 492 492 -1 -1
6652 6652 756 756 -1 -1
7301 7301 280 280 -1 -1
4286 4286 9441 9441 -1 -1
3865 3865 9689 9689 -1 -1
8444 8444 6619 6619 -1 -1
8440 8440 4729 4729 -1 -1
8031 8031 8117 8117 -1 -1
8097 8097 5771 5771 -1 -1
4481 4481 675 675 -1 -1
709 709 8927 8927 -1 -1
4567 4567 7856 7856 -1 -1
9497 9497 2353 2353 -1 -1
4586 4586 6965 6965 -1 -1
5306 5306 4683 4683 -1 -1
6219 6219 8624 8624 -1 -1
1528 1528 2871 2871 -1 -1
5732 5732 8829 8829 -1 -1
9503 9503 19 19 -1 -1
8270 8270 3368 3368 -1 -1
9708 9708 6715 6715 -1 -1
6340 6340 8149 8149 -1 -1
7796 7796 723 723 -1 -1
2618 2618 2245 2245 -1 -1
2846 2846 3451 3451 -1 -1
2921 2921 3555 3555 -1 -1
2379 2379 7488 7488 -1 -1
7764 7764 8228 8228 -1 -1
9841 9841 2350 2350 -1 -1
5193 5193 1500 1500 -1 -1
7034 7034 7764 7764 -1 -1
124 124 4914 4914 -1 -1
6987 6987 5856 5856 -1 -1
3743 3743 6491 6491 -1 -1
2227 2227 8365 8365 -1 -1
9859 9859 1936 1936 -1 -1
1432 1432 2551 2551 -1 -1
6437 6437 9228 9228 -1 -1
3275 3275 5407 5407 -1 -1
1474 1474 6121 6121 -1 -1
8858 8858 4395 4395 -1 -1
6029 6029 1237 1237 -1 -1
8235 8235 3793 3793 -1 -1
5818 5818 4428 4428 -1 -1
6143 6143 1011 1011 -1 -1
5928 5928 9529 9529 -1 -1

4.out：

5.in：

1 1 10001 10001
9383 9389 2777 2782 -1 -1
7793 7798 5386 5388 -1 -1
6649 6650 2362 2369 -1 -1
8690 8699 7763 7769 -1 -1
540 546 9172 9178 -1 -1
5211 5219 2567 2576 -1 -1
5782 5782 2862 2865 -1 -1
4067 4072 3929 3931 -1 -1
4022 4030 3069 3076 -1 -1
1393 1399 5011 5013 -1 -1
6229 6232 4421 4430 -1 -1
3784 3791 5198 5202 -1 -1
8315 8315 6413 6419 -1 -1
6091 6091 9956 9959 -1 -1
6862 6862 6996 6997 -1 -1
2305 2310 7084 7091 -1 -1
336 341 846 855 -1 -1
1313 1320 6124 6129 -1 -1
9582 9587 8814 8821 -1 -1
5434 5438 4043 4043 -1 -1
1087 1095 7276 7284 -1 -1
5788 5792 5403 5404 -1 -1
2754 2763 9932 9932 -1 -1
9676 9684 7739 7741 -1 -1
6226 6232 8094 8103 -1 -1
795 795 1434 1442 -1 -1
7467 7468 97 99 -1 -1
3317 3319 6652 6658 -1 -1
7301 7301 4286 4287 -1 -1
3865 3874 8444 8453 -1 -1
8440 8449 8031 8038 -1 -1
8097 8098 4481 4486 -1 -1
709 716 4567 4573 -1 -1
9497 9500 4586 4591 -1 -1
5306 5309 6219 6223 -1 -1
1528 1529 5732 5741 -1 -1
9503 9512 8270 8278 -1 -1
9708 9713 6340 6349 -1 -1
7796 7799 2618 2623 -1 -1
2846 2847 2921 2926 -1 -1
2379 2387 7764 7772 -1 -1
9841 9841 5193 5193 -1 -1
7034 7038 124 128 -1 -1
6987 6993 3743 3744 -1 -1
2227 2232 9859 9865 -1 -1
1432 1433 6437 6445 -1 -1
3275 3282 1474 1475 -1 -1
8858 8863 6029 6036 -1 -1
8235 8238 5818 5826 -1 -1
6143 6144 5928 5937 -1 -1
8776 8780 4443 4446 -1 -1
4613 4621 8606 8606 -1 -1
2904 2912 5128 5136 -1 -1
7369 7376 9917 9923 -1 -1
3324 3327 9470 9473 -1 -1
8490 8499 9772 9777 -1 -1
5644 5644 7505 7514 -1 -1
2954 2960 7669 7671 -1 -1
8542 8546 197 204 -1 -1
9355 9359 6348 6349 -1 -1
3622 3630 9299 9302 -1 -1
5746 5754 4340 4342 -1 -1
3311 3311 7605 7606 -1 -1
5661 5661 4878 4883 -1 -1
9320 9326 9444 9450 -1 -1
8522 8527 6708 6714 -1 -1
8282 8290 2924 2931 -1 -1
2062 2066 2600 2606 -1 -1
3452 3461 9379 9379 -1 -1
7468 7469 973 974 -1 -1
3881 3881 8933 8937 -1 -1
8660 8663 7199 7200 -1 -1
8899 8905 2959 2962 -1 -1
2813 2821 7190 7195 -1 -1
2926 2932 5084 5084 -1 -1
2090 2094 3376 3378 -1 -1
5936 5943 7445 7451 -1 -1
9179 9187 6887 6889 -1 -1
3348 3350 1659 1668 -1 -1
2336 2336 6342 6349 -1 -1
8206 8207 7713 7715 -1 -1
5321 5326 4819 4828 -1 -1
7721 7725 5939 5940 -1 -1
3940 3947 1705 1713 -1 -1
1127 1127 5984 5992 -1 -1
3920 3924 2422 2431 -1 -1
1396 1397 5630 5634 -1 -1
9292 9294 7672 7672 -1 -1
7625 7630 1222 1231 -1 -1
6640 6642 3898 3901 -1 -1
2298 2298 524 524 -1 -1
8209 8210 8819 8825 -1 -1
7732 7737 5994 5998 -1 -1
379 388 5273 5279 -1 -1
8850 8855 1860 1862 -1 -1
5579 5583 1993 1998 -1 -1
7621 7628 2504 2507 -1 -1
1961 1965 1326 1335 -1 -1
8944 8946 3202 3208 -1 -1
6784 6785 2842 2850 -1 -1

5.out：

没有啦，还看呢，如果这些都过了，还是WA那真的难受。

POJ ~ 2502 ~ Subway （Dijkstra + 建图）

相关阅读

相关文章

相关问答

相关文档