Indecisive Taxi Fee
题目链接：luogu CF1163F
题目大意
给你一个无向图，每次改一条边的权值（每次都会变回来），问你 1~n 的最短路长度。
思路
考虑分类讨论，先找到最短路的路径，然后看修改的边在不在最短路上。
如果不在，要么还是原来的最短路，要么就是你这条边 \((x,y)\) 从 \(1\) 到 \(x\) 的最短路加上你的新边权再加上 \(y\) 到 \(n\) 的最短路。
然后 \(1,n\) 到所有点的最短路我们预处理出来就可以弄。
然后就是在最短路，那要么是原来的最短路优，要么是你新找一条最短路它不经过你改的这条边（就是把它删了跑最短路）。
发现只有这个新找路要求，考虑一下这条路的性质。
发现一定能找一条，它肯定是跟最短路有一个前缀，一个后缀，中间的部分不会跟最短路的边有交集。
因为有交集，假设分成两半，你把不是删了的边的那一半改成最短路，那更短或者一样啊。
然后你就看每条不在最短路上的边，如果要他走这条边作为最短路，它能代替那些最短路上的边。
那根据前面，代替的也是一个区间的。
于是考虑求这个区间。
对于每个点，你有一个 \(L_i\) 表示最小的 \(x\)，使得 \(1\rightarrow i\) 的路上 \(e_x\) 这条边是第一个不在最短路上的边
（\(e_i\) 是最短路的边）
\(R_i\) 表示最大的 \(x\) 使得 \(x\rightarrow 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<set>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#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;
}