AK-dream

题目描述

JOI 王国共有 $N$ 个城市,这些城市从 $1$ 到 $N$ 编号。共有 $M$ 条公交线路连接这些城市,这些线路从 $1$ 到 $M$ 编号。第 $i$ 条公交线是从城市 $U_i$ 到城市 $V_i$ 的,票价为 $C_i$ 日元。如果乘客乘坐第 $i$ 条公交线,他只能在城市 $U_i$ 上车,在城市 $V_i$ 下车。从一个城市到另一个城市可能有多条公交线。

不久,JOI 王国将举办奥运会。K 理事长是 JOI 王国交通部部长。他会在奥运会之前选择最多一条公交线,并翻转这条公交线的起点和终点,但不改变票价。换句话说,如果他选择第 条公交线,在奥运会期间它将不会从 $U_i$ 城市开往 $V_i$ 城市,而是从 $V_i$ 城市开往 $U_i$ 城市,但票价仍为 $C_i$ 日元。翻转一条公交线需要 $D_i$ 日元,并且这个钱是 K 理事长出的。为了避免迷惑行为,在奥运会期间不允许翻转公交线。

因为 K 理事长是 JOI 王国的交通部部长,在奥运会期间他会使用这些公交线在城市 $1$ 和城市 $N$ 之间往返。通过恰当地选择翻转某条(或不翻转任何)公交线,他想要最小化往返城市 $1$ 和城市 $N$ 的公交总票价与翻转公交线的代价和。

现给定城市数和公交线情况,写一个程序求出这个最小代价和。如果不能通过翻转某条公交线来达到往返城市 $1$ 与城市 $N$ 的目的,请输出 $-1$。

输入格式

第一行两个整数 $N,M$,意义如题目描述;

接下来 $M$ 行,每行四个整数 $U_i,V_i,C_i,D_i$,意义如题目描述。

输出格式

输出一行一个整数,如果可以通过翻转某条(或不翻转任何)公交线使得可以往返于城市 $1$ 与城市 $N$,输出往返所需公交总票价与翻转公交线的代价和的最小值,否则输出 $-1$。

题解

翻转一条边 $u,v$ 后 $1$ 到 $N$ 的最短路:

(1) 不经过翻转后的边 $v,u$ :

由于这种情况中我们不经过这条边 所以可以看作是删除了这条边

如果 $u,v$ 在以 $1$ 为源的最短路树上,那么删除这条边之后 $1$ 到 $N$ 的最短路可能会发生变化,需要重新跑一次 dijkstra (注意是不经过边 $u,v$ 的)

如果不在最短路树上,则删除该边后 $1$ 到 $N$ 的最短路一定和原来的一样

(2) 经过翻转后的边 $v,u$ :

此时 $1$ 到 $N$ 的最短路为:

$1$ 到 $v$ 的不经过边 $u,v$ 的最短路 + $u$ 到 $N$ 的不经过边 $u,v$ 的最短路 + $\mathrm{dis}(v,u)$

求 $1$ 到 $v$ 的不经过边 $u,v$ 的最短路同(1)

求 $u$ 到 $N$ 的不经过边 $u,v$ 的最短路 可以在反图上找出以 $N$ 为源的最短路树,然后判断 $u,v$ 是否在这棵最短路树上,同(1)一样进行分类讨论

对于每条边 $i$,我们可以开一个 $mn[i]$ 取上面两种情况的最小值,这就是翻转边 $u_i,v_i$ 后 $1$ 到 $N$ 的最短路

翻转某边后 $N$ 到 $1$ 的最短路同理,可以存在 $mn2[i]$ 中

那么答案就是 $\min_{i=1}^{m} mn[i]+mn2[i]+D_i$

最后记得计算一下不翻转边时的总代价

p.s. inf最好不要设得太大 不然好几个inf加一起就爆longlong了

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
#define M 100005
using namespace std;
typedef long long ll;

template<typename T>
inline void read(T &num) {
T x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
num = x * f;
}

const ll inf = 1e16;
int n, m;
int head[205][2], lst[205][2], from[M][2], pre[M][2], to[M][2], sz[2]; //0:原图 1:反图
ll c[M][2], d[M][2], ans, mn[M][2];
bool ok[M][2];

inline void addedge(int u, int v, ll w, ll w2, int tp) {
pre[++sz[tp]][tp] = head[u][tp]; head[u][tp] = sz[tp]; ok[sz[tp]][tp] = 1;
from[sz[tp]][tp] = u; to[sz[tp]][tp] = v; c[sz[tp]][tp] = w; d[sz[tp]][tp] = w2;
}

priority_queue<pair<ll, int> > q;
ll dis[205][2], tmp[205];
bool vis[205], tag[M][2];
void dijkstra(int s, int tp) {
for (int i = 1; i <= n; i++) dis[i][tp] = inf;
dis[s][tp] = 0;
memset(vis, 0, sizeof(vis));
q.push(make_pair(0, s));
while (!q.empty()) {
int x = q.top().second; q.pop();
if (vis[x]) continue;
vis[x] = 1;
for (int i = head[x][tp]; i; i = pre[i][tp]) {
int y = to[i][tp];
if (dis[y][tp] > dis[x][tp] + c[i][tp]) {
dis[y][tp] = dis[x][tp] + c[i][tp];
lst[y][tp] = i;
q.push(make_pair(-dis[y][tp], y));
}
}
}
}

void tmp_dij(int s, int tp) {
for (int i = 1; i <= n; i++) tmp[i] = inf;
tmp[s] = 0;
memset(vis, 0, sizeof(vis));
q.push(make_pair(0, s));
while (!q.empty()) {
int x = q.top().second; q.pop();
if (vis[x]) continue;
vis[x] = 1;
for (int i = head[x][tp]; i; i = pre[i][tp]) {
int y = to[i][tp];
if (!ok[i][tp]) continue;
if (tmp[y] > tmp[x] + c[i][tp]) {
tmp[y] = tmp[x] + c[i][tp];
q.push(make_pair(-tmp[y], y));
}
}
}
}

void solve(int s, int t, int o) {
dijkstra(s, 0);
dijkstra(t, 1);
memset(tag, 0, sizeof(tag));
for (int i = 1; i <= n; i++) {
tag[lst[i][0]][0] = 1;
tag[lst[i][1]][0] = 1;
}
for (int i = 1; i <= sz[0]; i++) {
int u = from[i][0], v = to[i][0];
ll now = c[i][0];
if (!tag[i][0]) {
mn[i][o] = dis[t][0];
now += dis[v][0];
} else {
ok[i][0] = 0;
tmp_dij(s, 0);
ok[i][0] = 1;
mn[i][o] = tmp[t];
now += tmp[v];
}
if (!tag[i][1]) {
now += dis[u][1];
} else {
ok[i][1] = 0;
tmp_dij(t, 1);
ok[i][1] = 1;
now += tmp[u];
}
mn[i][o] = min(mn[i][o], now);
}
}

int main() {
read(n); read(m);
for (int i = 1, u, v; i <= m; i++) {
ll cc, dd;
read(u); read(v); read(cc); read(dd);
addedge(u, v, cc, dd, 0);
addedge(v, u, cc, dd, 1);
}
ans = inf; ll now = 0;
dijkstra(1, 0); now += dis[n][0];
dijkstra(n, 0); now += dis[1][0];
ans = min(ans, now);
solve(1, n, 0);
solve(n, 1, 1);
for (int i = 1; i <= sz[0]; i++) {
ans = min(ans, mn[i][0] + mn[i][1] + d[i][0]);
}
printf("%lld\n", ans >= inf ? -1 : ans);
return 0;
}

 评论