P9549 「PHOI-1」路虽远题解

FiraCode · 2023-08-16 19:37:30 · 题解

路虽远题解

题意：

给你一个 n 个点 m 条边的图，从一个节点出发到另一个节点时可能要等红绿灯，可以闯黄灯 g 次，要在 k 条边上添加限速，限速会使小 X 经过这条边的时间变长，求小 X 从第一个节点到第 n 个节点的最短时间。

Subtask0

可以直接爆搜，让后每次就记录当前时间，当前节点，以及还剩多少条边需要限速，以及还可以闯多少次黄灯，因为可以通过每个灯的时间算出来当前是哪个灯，然后判断要不要闯黄灯，以及需要等多长时间。

得分：20pts。

Subtask1

因为只有绿灯，而且无法闯红灯，没有限速，那么就直接对原图跑最短路就可以了。

加上前面的 Subtask 可以拿 25 分。

Subtask2

没有黄灯，也就是无法闯黄灯。

那么考虑如何做限速。

因为相当于修改 k 条边的边权，那么可以考虑分层图。

那么可以考虑都限速，然后建 m - k 层，每层由不限速的边连起来，这样到达最后一层中相当于第一层的的 n 个点（后面统称为终点），就相当于一定有 k 条边是限速的（因为最多走 m - k 条不限速的边）。

然后再把每一层的终点向最后一层的终点连一条边权为 0 的边连起来，这样能保证走不足 m - k 条不限速的边可以直接到达。

最后就输出到达终点的最短距离即可，因为 spfa 会被卡，所以要用堆优化的 dijkstra。

加上前面的 Subtask 可以拿 50。

Subtask3

其实可以使用三维的 dijkstra，每一维分别表示当前是那个点，当前还剩多少条边可以不限速，当前还可以闯多少黄灯。

设当前时刻为 t。

• 1.若还可以不限速：

  则有两种情况：

  • 1.不闯黄灯，则判断当前时刻当前路口是否为绿灯，若是则可以直接冲过去，权值为不限速的权值，否则就加上等红绿灯的时间，也就是灯亮的总时间减去当前时刻 t，也就是总时间减去已经过去的时间。
  • 2.闯黄灯，那么当前是绿灯或者黄灯时间，那么可以直接冲过去，否则再加上等红绿灯的时间即可。

• 2.若不可以不限速：

  同上，只不过把通过的时间改为限速的权值即可。

按照权值跑 dijkstra 即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 110, M = N << 1;
const int INF = 1ll << 60;

int n, m, k, g;
int a[N], b[N], c[N], dist[N][N][N];
int h[N], e[M], ne[M], p[M], q[M], idx;

struct Node {
    int x, y, z, w;
    const bool operator<(const Node &x) const{
        return w > x.w;
    }
};
priority_queue<Node> q1;

void add(int a, int b, int n, int m) {
    e[idx] = b, p[idx] = n, q[idx] = m, ne[idx] = h[a], h[a] = idx++;
}

void update(int x, int y, int z, int w) {
    if (dist[x][y][z] > w) {
        dist[x][y][z] = w;
        q1.push({x, y, z, w});
    }
}

void dijkstra() {
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= k; ++j)
            for (int k = 0; k <= g; ++k)
                dist[i][j][k] = INF;

    dist[1][0][0] = 0;
    q1.push({1, 0, 0, 0});

    while (!q1.empty()) {
        auto u = q1.top();
        q1.pop();
        int x = u.x, y = u.y, z = u.z, w = u.w, now = w % (a[x] + b[x] + c[x]);
        if (dist[x][y][z] < w) continue;
        for (int i = h[x]; ~i; i = ne[i]) {
            int v = e[i];
            if (y < k) {
                if (now < a[x]) update(v, y + 1, z, w + p[i]);
                else update(v, y + 1, z, w + a[x] + b[x] + c[x] - now + p[i]);
                if (z < g) {
                    if (now < (a[x] + b[x])) update(v, y + 1, z + 1, w + p[i]);
                    else update(v, y + 1, z + 1, w + a[x] + b[x] + c[x] - now + p[i]);
                }
            }
            if (now < a[x]) update(v, y, z, w + q[i]);
            else update(v, y, z, w + a[x] + b[x] + c[x] - now + q[i]);
            if (z < g) {
                if (now < (a[x] + b[x])) update(v, y, z + 1, w + q[i]);
                else update(v, y, z + 1, w + a[x] + b[x] + c[x] - now + q[i]);
            }
        }
    }
}

signed main() {
    memset(h, -1, sizeof(h));
    scanf("%lld%lld%lld%lld", &n, &m, &k, &g);
    k = m - k;

    for (int i = 1; i <= n; ++i) scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);

    for (int i = 1; i <= m; ++i) {
        int u, v, p, q;
        scanf("%lld%lld%lld%lld", &u, &v, &p, &q);
        add(u, v, p, q);
        add(v, u, p, q);
    }

    dijkstra();
    int ans = INF;

    for (int i = 0; i <= k; ++i)
        for (int j = 0; j <= g; ++j)
            ans = min(ans, dist[n][i][j]);

    if (ans == INF) puts("-1");
    else printf("%lld\n", ans);

    return 0;
}