P8724 题解

CodingShark · 2022-12-26 09:55:07 · 题解

显然是分层图最短路的板子题，拆两段限高杆，因此建 3 层图。

如果一条道路没有限高杆，则：

• 第一层在 u, v 之间连双向边

• 第二层在 u, v 之间连双向边

• 第三层在 u, v 之间连双向边

如果一条道路有限高杆，则：

• 第一层 u 与第二层 v 连边

• 第一层 v 与第二层 u 连边（注意无向图，一定是双向边！！）

• 第二层 u 与第三层 v 连边

• 第三层 v 与第二层 u 连边（注意无向图，一定是双向边！！）

当然在实际跑最短路路时不需要明确分层，用 u,u+n,u+2n 表示这三层的节点就可以了。

但是注意到就算拆了限高杆货车也可能不走那条道路，所以相邻两层直接对应的点也需要连一条边权为 0 的边。

#include <bits/stdc++.h>
using namespace std;
struct Edge
{
    int u, v, w, next;
} e[1000005];
struct state
{
    int dis, v;
    bool operator<(const state t) const
    {
        return dis > t.dis;
    }
};
int n, m, pos, head[100005], dis[100005];
bool vis[100005];
void addEdge(int u, int v, int w)
{
    e[++pos] = {u, v, w, head[u]};
    head[u] = pos;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int u, v, w, op;
        scanf("%d%d%d%d", &u, &v, &w, &op);
        if (op & 1)
        {
            addEdge(u, v + n, w);
            addEdge(v, u + n, w);
            addEdge(u + n, v + 2 * n, w);
            addEdge(v + n, u + 2 * n, w);
        }
        else
        {
            addEdge(u, v, w);
            addEdge(v, u, w);
            addEdge(u + n, v + n, w);
            addEdge(v + n, u + n, w);
            addEdge(u + 2 * n, v + 2 * n, w);
            addEdge(v + 2 * n, u + 2 * n, w);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        addEdge(i, i + n, 0);
        addEdge(i + n, i + 2 * n, 0);
    }
    dij(1); // Dijkstra 最短路，就不用贴上来了吧
    printf("%d", dis[n] - dis[3 * n]); // dis[n] 是原图最短路
    return 0;
}