题目(abc395)

E - 翻转边

时间限制：2秒 / 内存限制：1024 MB

分数：425分

问题描述

给定一个有向图，包含 N 个顶点和 M 条边。第 i 条边为从顶点 u_i 到顶点 v_i 的有向边。

初始时，你在顶点 1，你希望通过以下操作直到到达顶点 N：

执行以下两种操作之一：

  1. 沿着一条有向边从当前顶点移动，消耗的代价为 1。具体地，如果你在顶点 v，选择一个顶点 u，使得存在从 v 到 u 的有向边，并移动到顶点 u。
  2. 反转所有边的方向，消耗的代价为 X。具体地，只有当在此操作之前，存在从顶点 v 到顶点 u 的有向边时，在操作之后，才会存在从顶点 u 到顶点 v 的有向边。

保证对于给定的图，重复这些操作后，你一定能从顶点 1 到达顶点 N。

请你计算到达顶点 N 所需的最小总代价。

约束条件

  • 2 ≤ N ≤ 2 × 10^5
  • 1 ≤ M ≤ 2 × 10^5
  • 1 ≤ X ≤ 10^9
  • 1 ≤ u_i ≤ N (1 ≤ i ≤ M)
  • 1 ≤ v_i ≤ N (1 ≤ i ≤ M)

输入

输入通过标准输入给出，格式如下：

1
2
3
4
5
N M X
u1 v1
u2 v2
...
uM vM

输出

输出一个整数，表示到达顶点 N 所需的最小总代价。

样例输入 1

1
2
3
4
5
6
7
5 6 5
1 2
2 4
3 1
3 5
4 3
5 2

样例输出 1

1
4

题解

  • 代价即为边的权重
  • 由题意可以建立双层图，一层正向，一层反向
  • 正向图节点下标范围[1, n]，反向图节点下标范围[1+n, n+n]，这样就能避免冲突
  • 添加边(u->v)的同时添加边(v+n->u+n)
  • 而从一层图的u点到另一层图的u点的距离为x
  • 建立两层图之间对应点的双向连接之后即可将其合并作普通有向图，使用dijkstra
  • 最后的答案是min(dis[n], dis[n<<1])

代码与注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;
// (dis, pos)
#define PII pair<long long, int> 
const int N = 2e5+10;
int n, m;
long long x;
long long dis[N<<1];
bool vis[N<<1];
struct edge
{
    int to;
    long long d;
};
vector<edge> dot[N<<1];
void add_edge(int u, int v, long long d) {
    dot[u].push_back((edge){v, d}); // 建立点v的邻接表
}
priority_queue<PII, vector<PII>, greater<PII>> q;

void dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    q.push(make_pair(0, 1));
    while (!q.empty()) {
        PII tmp = q.top();
        q.pop();
        if(vis[tmp.second]) {
            continue;
        }
        int pos = tmp.second;
        long long d = tmp.first;
        vis[pos] = 1;
        for(edge e : dot[pos]) {
            int v = e.to;
            if(vis[v]) continue;
            if(dis[v] > d + e.d) {
                dis[v] = d+e.d;
                q.push(make_pair(dis[v], v));
            }
        }
    }
}

int main() {
    scanf("%d%d%lld", &n, &m, &x);
    int u, v;
    for(int i=0; i<m; i++) {
        scanf("%d%d", &u, &v);
        add_edge(u, v, 1), add_edge(v+n, u+n, 1); // 建立一层正向图 一层反向图
    }
    for(int i=1; i<=n; i++) {
        add_edge(i, i+n, x);
        add_edge(i+n, i, x);
    }
    dijkstra();
    long long ans = min(dis[n], dis[n<<1]);
    printf("%lld\n", ans);
    return 0;
}