题目描述

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;
}

评论