AK-dream

奥运公交[LOJ3255]

AK-dream

发布于：2020年7月31日
次浏览

题目描述

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

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://akdream.tk/post/b8eba3fa.html/

更新于：2020年9月7日

最短路

评论