Skip to content

L2-001 紧急救援

Statement

Metadata

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

作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。

输入格式

输入第一行给出4个正整数N、M、S、D，其中N（2\le N\le 500）是城市的个数，顺便假设城市的编号为0 ~ (N-1)；M是快速道路的条数；S是出发地的城市编号；D是目的地的城市编号。

第二行给出N个正整数，其中第i个数是第i个城市的救援队的数目，数字间以空格分隔。随后的M行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。

输出格式

第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。

输入样例 

4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2

输出样例 

2 60
0 1 3

Solution

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

#define N 510
#define INF 0x3f3f3f3f
struct Graph {
    struct node {
        int to, nx, w;
        node() {}
        node(int to, int nx, int w) : to(to), nx(nx), w(w) {}
    } a[N * N];
    int head[N], pos;
    void init() {
        memset(head, -1, sizeof head);
        pos = 0;
    }
    void add(int u, int v, int w) {
        a[++pos] = node(v, head[u], w);
        head[u] = pos;
        a[++pos] = node(u, head[v], w);
        head[v] = pos;
    }
} G;
#define erp(u) \
    for (int it = G.head[u], v = G.a[it].to, w = G.a[it].w; ~it; it = G.a[it].nx, v = G.a[it].to, w = G.a[it].w)
int n, m, st, ed;
int val[N];

struct node {
    int u, a, b, fa;
    node() {}
    node(int u, int a, int b, int fa) : u(u), 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];
int tot[N], fa[N];
bool used[N];
void Dij() {
    for (int i = 0; i < n; ++i) {
        used[i] = 0;
        dist[i][0] = INF;
        dist[i][1] = 0;
        tot[i] = 0;
    }
    tot[st] = 1;
    dist[st][0] = 0;
    dist[st][1] = val[st];
    priority_queue<node> pq;
    pq.push(node(st, dist[st][0], dist[st][1], -1));
    while (!pq.empty()) {
        int u = pq.top().u, pre = pq.top().fa;
        pq.pop();
        if (used[u])
            continue;
        used[u] = 1;
        fa[u] = pre;
        if (u == ed) {
            vector<int> ord;
            while (u != -1) {
                ord.push_back(u);
                u = fa[u];
            }
            reverse(ord.begin(), ord.end());
            printf("%d %d\n", tot[ed], dist[ed][1]);
            for (int i = 0, len = ord.size(); i < len; ++i) printf("%d%c", ord[i], " \n"[i == len - 1]);
            return;
        }
        erp(u) {
            if (dist[v][0] > dist[u][0] + w) {
                dist[v][0] = dist[u][0] + w;
                dist[v][1] = dist[u][1] + val[v];
                tot[v] = tot[u];
                pq.push(node(v, dist[v][0], dist[v][1], u));
            } else if (dist[v][0] == dist[u][0] + w) {
                tot[v] += tot[u];
                if (dist[v][1] < dist[u][1] + val[v]) {
                    dist[v][1] = dist[u][1] + val[v];
                    pq.push(node(v, dist[v][0], dist[v][1], u));
                }
            }
        }
    }
}

int main() {
    scanf("%d%d%d%d", &n, &m, &st, &ed);
    for (int i = 0; i < n; ++i) scanf("%d", val + i);
    G.init();
    for (int i = 1, u, v, w; i <= m; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        G.add(u, v, w);
    }
    Dij();
    return 0;
}
Last update: May 4, 2022
Back to top