【luogu CF1163F】Indecisive Taxi Fee（图论）（分类讨论）

Indecisive Taxi Fee

题目链接：luogu CF1163F

题目大意

给你一个无向图，每次改一条边的权值（每次都会变回来），问你 1~n 的最短路长度。

思路

考虑分类讨论，先找到最短路的路径，然后看修改的边在不在最短路上。

如果不在，要么还是原来的最短路，要么就是你这条边 $(x,y)$ 从 $1$ 到 $x$ 的最短路加上你的新边权再加上 $y$ 到 $n$ 的最短路。
然后 $1,n$ 到所有点的最短路我们预处理出来就可以弄。

然后就是在最短路，那要么是原来的最短路优，要么是你新找一条最短路它不经过你改的这条边（就是把它删了跑最短路）。
发现只有这个新找路要求，考虑一下这条路的性质。

发现一定能找一条，它肯定是跟最短路有一个前缀，一个后缀，中间的部分不会跟最短路的边有交集。
因为有交集，假设分成两半，你把不是删了的边的那一半改成最短路，那更短或者一样啊。

然后你就看每条不在最短路上的边，如果要他走这条边作为最短路，它能代替那些最短路上的边。
那根据前面，代替的也是一个区间的。
于是考虑求这个区间。

对于每个点，你有一个 $L_i$ 表示最小的 $x$，使得 $1\to i$ 的路上 $e_x$ 这条边是第一个不在最短路上的边
（$e_i$ 是最短路的边）
$R_i$ 表示最大的 $x$ 使得 $x\to n$ 的路上 $e_x$ 这条边是最后一个不在最短路上的边。
那这个我们可以 DP，一开始对于最短路上的点，有 $L_x=i,R_x=i$（$i$ 是 $x$ 是第几个点）

然后你按从 $1$ 开始的最短路树的顺序，和 $n$ 开始的最短路树的顺序，分别 DP $L_i,R_i$，就直接选不在最短路上的边，儿子跟它取 $\min ,\max$ 即可。
那求出来点，接着看边的，那就根据 $L_x,R_y$ 确定一下 $x,y$，只要有区间就行那种，那这个就是那个区间了。
那怎么求所有边的答案呢？因为有很多个区间可以选。
会发现对于里面能替换掉的所有最短路上的边，替换之后走的距离都是一样的。

然后你考虑一个指针从左往右扫，最左侧放入，最右侧弹出，维护一个 multiset，每次答案就是最小值。
当然你用线段树搞也可以。

代码

#include
#include
#include
#include
#include 
#define ll long long
using namespace std;

const ll N = 2e5 + 1000;
struct node {
	ll x, to, nxt, id;
}e[N << 1];
ll n, m, q, le[N], KK, dian[N], bian[N];
ll xxx[N], yyy[N], zzz[N], pl[N], ib[N];
ll L[N], R[N];
ll miss[N];

void add(ll x, ll y, ll z, ll id) {
	e[++KK] = (node){z, y, le[x], id}; le[x] = KK;
}

bool cant[N];
struct Work {
	ll S, fr[N], frid[N];
	ll f[N];
	bool in[N];
	
	void work() {
		priority_queue <pair<ll, ll>, vector<pair<ll, ll> >, greater<pair<ll, ll> > > q;
		while (!q.empty()) q.pop(); memset(in, 0, sizeof(in));
		memset(f, 0x3f, sizeof(f)); f[S] = 0; q.push(make_pair(0, S));
		while (!q.empty()) {
			ll now = q.top().second; q.pop();
			if (in[now]) continue; in[now] = 1;
			for (ll i = le[now]; i; i = e[i].nxt)
				if (!cant[e[i].id] && f[e[i].to] > f[now] + e[i].x) {
					f[e[i].to] = f[now] + e[i].x; fr[e[i].to] = now; frid[e[i].to] = e[i].id;
					q.push(make_pair(f[e[i].to], e[i].to));
				}
		}
	}
	
	void get_road(ll T) {
		ll now = T;
		while (now != S) {
			cant[frid[now]] = 1; bian[++bian[0]] = frid[now]; dian[++dian[0]] = now; now = fr[now];
		}
		dian[++dian[0]] = now; reverse(dian + 1, dian + dian[0] + 1);
		reverse(bian + 1, bian + bian[0] + 1);
	}
}T1, Tn;

bool cmp1(ll x, ll y) {
	return T1.f[x] < T1.f[y];
}
bool cmpn(ll x, ll y) {
	return Tn.f[x] < Tn.f[y];
}
multiset <ll> qq;
vector <ll> up[N], down[N];

int main() {
	scanf("%lld %lld %lld", &n, &m, &q);
	for (ll i = 1; i <= m; i++) {
		ll x, y, z; scanf("%lld %lld %lld", &x, &y, &z);
		add(x, y, z, i); add(y, x, z, i);
		xxx[i] = x; yyy[i] = y; zzz[i] = z;
	}
	
	T1.S = 1; Tn.S = n;
	T1.work(); Tn.work();
	T1.get_road(n);
	
	for (ll i = 1; i <= bian[0]; i++) ib[bian[i]] = i;
	memset(L, 0x3f, sizeof(L));
	for (ll i = 1; i <= dian[0]; i++) L[dian[i]] = i, R[dian[i]] = i;
	for (ll i = 1; i <= n; i++) pl[i] = i;
	sort(pl + 1, pl + n + 1, cmp1);
	for (ll i = 1; i <= n; i++) {
		ll now = pl[i];
		for (ll j = le[now]; j; j = e[j].nxt)
			if (!cant[e[j].id] && T1.f[e[j].to] == T1.f[now] + e[j].x)
				L[e[j].to] = min(L[e[j].to], L[now]);
	}
	sort(pl + 1, pl + n + 1, cmpn);
	for (ll i = 1; i <= n; i++) {
		ll now = pl[i];
		for (ll j = le[now]; j; j = e[j].nxt)
			if (!cant[e[j].id] && Tn.f[e[j].to] == Tn.f[now] + e[j].x)
				R[e[j].to] = max(R[e[j].to], R[now]);
	}
	for (ll i = 1; i <= m; i++) if (!cant[i]) {
		ll x = xxx[i], y = yyy[i];
		if (L[x] <= R[y] - 1) {
			ll val = T1.f[x] + zzz[i] + Tn.f[y];
			up[L[x]].push_back(val); down[R[y] - 1].push_back(val);
		}
		swap(x, y);
		if (L[x] <= R[y] - 1) {
			ll val = T1.f[x] + zzz[i] + Tn.f[y];
			up[L[x]].push_back(val); down[R[y] - 1].push_back(val);
		}
	}
	memset(miss, 0x3f, sizeof(miss)); 
	for (ll i = 1; i <= dian[0]; i++) {
		for (ll j = 0; j < up[i].size(); j++) qq.insert(up[i][j]);
		if (!qq.empty()) miss[i] = *qq.begin();
		for (ll j = 0; j < down[i].size(); j++) qq.erase(qq.find(down[i][j]));
	}
	
	while (q--) {
		ll x, y; scanf("%lld %lld", &x, &y);
		if (cant[x]) {//在最短路 
			printf("%lld\n", min(miss[ib[x]], T1.f[n] - zzz[x] + y));
		}
		else {//不在最短路 
			printf("%lld\n", min(T1.f[n], min(T1.f[xxx[x]] + y + Tn.f[yyy[x]], T1.f[yyy[x]] + y + Tn.f[xxx[x]])));
		}
	}
	
	return 0;
}
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
121
122