Skip to content

L3-007 天梯地图

Statement

Metadata

  • 作者: 陈越
  • 单位: 浙江大学
  • 代码长度限制: 16 KB
  • 时间限制: 300 ms
  • 内存限制: 64 MB

本题要求你实现一个天梯赛专属在线地图，队员输入自己学校所在地和赛场地点后，该地图应该推荐两条路线：一条是最快到达路线；一条是最短距离的路线。题目保证对任意的查询请求，地图上都至少存在一条可达路线。

输入格式

输入在第一行给出两个正整数N（2 \le N \le 500）和M，分别为地图中所有标记地点的个数和连接地点的道路条数。随后M行，每行按如下格式给出一条道路的信息：

V1 V2 one-way length time

其中V1和V2是道路的两个端点的编号（从0到N-1）；如果该道路是从V1到V2的单行线，则one-way为1，否则为0；length是道路的长度；time是通过该路所需要的时间。最后给出一对起点和终点的编号。

输出格式

首先按下列格式输出最快到达的时间T和用节点编号表示的路线：

Time = T: 起点 => 节点1 => ... => 终点

然后在下一行按下列格式输出最短距离D和用节点编号表示的路线：

Distance = D: 起点 => 节点1 => ... => 终点

如果最快到达路线不唯一，则输出几条最快路线中最短的那条，题目保证这条路线是唯一的。而如果最短距离的路线不唯一，则输出途径节点数最少的那条，题目保证这条路线是唯一的。

如果这两条路线是完全一样的，则按下列格式输出：

Time = T; Distance = D: 起点 => 节点1 => ... => 终点

输入样例1 

10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
5 4 0 2 3
5 9 1 1 4
0 6 0 1 1
7 3 1 1 2
8 3 1 1 2
2 5 0 2 2
2 1 1 1 1
1 5 0 1 3
1 4 0 1 1
9 7 1 1 3
3 1 0 2 5
6 3 1 2 1
5 3

输出样例1 

Time = 6: 5 => 4 => 8 => 3
Distance = 3: 5 => 1 => 3

输入样例2 

7 9
0 4 1 1 1
1 6 1 3 1
2 6 1 1 1
2 5 1 2 2
3 0 0 1 1
3 1 1 3 1
3 2 1 2 1
4 5 0 2 2
6 5 1 2 1
3 5

输出样例2 

Time = 3; Distance = 4: 3 => 2 => 5

Solution

#include <bits/stdc++.h>
using namespace std;

#define N 1010
#define M 1000010
#define INF 0x3f3f3f3f
int n, m, st, ed;
struct Graph {
    struct node {
        int to, nx, l, t;
        node() {}
        node(int to, int nx, int l, int t) : to(to), nx(nx), l(l), t(t) {}
    } a[M << 1];
    int head[N], pos;
    void init() {
        memset(head, 0, sizeof head);
        pos = 0;
    }
    void add(int u, int v, int l, int t) {
        a[++pos] = node(v, head[u], l, t);
        head[u] = pos;
    }
} G;
#define erp(u)                                                                 \
    for (int it = G.head[u], v = G.a[it].to, l = G.a[it].l, t = G.a[it].t; it; \
            it = G.a[it].nx, v = G.a[it].to, l = G.a[it].l, t = G.a[it].t)
int Time, Dis;

namespace Dij {
struct node {
    int to, a, b, fa;
    node() {}
    node(int to, int a, int b, int fa) : to(to), a(a), b(b), fa(fa) {}
    bool operator<(const node &other) const {
        if (a != other.a)
            return a > other.a;
        return b > other.b;
    }
};

int dist[N][2], fa[N];
bool used[N];
void work1(vector<int> &res) {
    for (int i = 1; i <= n; ++i) {
        dist[i][0] = dist[i][1] = INF;
        fa[i] = -1;
        used[i] = 0;
    }
    dist[st][0] = dist[st][1] = 0;
    priority_queue<node> pq;
    pq.push(node(st, 0, 0, 0));
    while (!pq.empty()) {
        int u = pq.top().to, pre = pq.top().fa;
        pq.pop();
        if (used[u])
            continue;
        used[u] = 1;
        fa[u] = pre;
        if (u == ed) {
            Time = dist[u][0];
            int it = u;
            while (it) {
                res.push_back(it);
                it = fa[it];
            }
            reverse(res.begin(), res.end());
            return;
        }
        erp(u) {
            if (dist[v][0] > dist[u][0] + t) {
                dist[v][0] = dist[u][0] + t;
                dist[v][1] = dist[u][1] + l;
                pq.push(node(v, dist[v][0], dist[v][1], u));
            } else if (dist[v][0] == dist[u][0] + t && dist[v][1] > dist[u][1] + l) {
                dist[v][0] = dist[u][0] + t;
                dist[v][1] = dist[u][1] + l;
                pq.push(node(v, dist[v][0], dist[v][1], u));
            }
        }
    }
}
void work2(vector<int> &res) {
    for (int i = 1; i <= n; ++i) {
        dist[i][0] = dist[i][1] = INF;
        fa[i] = -1;
        used[i] = 0;
    }
    dist[st][0] = dist[st][1] = 0;
    priority_queue<node> pq;
    pq.push(node(st, 0, 0, 0));
    while (!pq.empty()) {
        int u = pq.top().to, pre = pq.top().fa;
        pq.pop();
        if (used[u])
            continue;
        used[u] = 1;
        fa[u] = pre;
        if (u == ed) {
            Dis = dist[u][0];
            int it = u;
            while (it) {
                res.push_back(it);
                it = fa[it];
            }
            reverse(res.begin(), res.end());
            return;
        }
        erp(u) {
            if (dist[v][0] > dist[u][0] + l) {
                dist[v][0] = dist[u][0] + l;
                dist[v][1] = dist[u][1] + 1;
                pq.push(node(v, dist[v][0], dist[v][1], u));
            } else if (dist[v][0] == dist[u][0] + l && dist[v][1] > dist[u][1] + 1) {
                dist[v][0] = dist[u][0] + l;
                dist[v][1] = dist[u][1] + 1;
                pq.push(node(v, dist[v][0], dist[v][1], u));
            }
        }
    }
}
}  // namespace Dij

bool same(vector<int> l, vector<int> r) {
    if ((int)l.size() != (int)r.size())
        return 0;
    int len = (int)l.size();
    for (int i = 0; i < len; ++i)
        if (l[i] != r[i])
            return 0;
    return 1;
}

void out(vector<int> vec) {
    int len = (int)vec.size();
    for (int i = 0; i < len; ++i) {
        printf("%d", vec[i] - 1);
        if (i != len - 1)
            printf(" => ");
        else
            printf("\n");
    }
}

int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        G.init();
        for (int i = 1, u, v, tp, l, t; i <= m; ++i) {
            scanf("%d%d%d%d%d", &u, &v, &tp, &l, &t);
            ++u, ++v;
            G.add(u, v, l, t);
            if (tp == 0)
                G.add(v, u, l, t);
        }
        scanf("%d%d", &st, &ed);
        ++st, ++ed;
        vector<int> res[2];
        Dij::work1(res[0]);
        Dij::work2(res[1]);
        if (same(res[0], res[1])) {
            printf("Time = %d; Distance = %d: ", Time, Dis);
            out(res[0]);
        } else {
            printf("Time = %d: ", Time);
            out(res[0]);
            printf("Distance = %d: ", Dis);
            out(res[1]);
        }
    }
    return 0;
}
Last update: May 4, 2022
Back to top