题解 - Tax最短路
给出一个 $n$ 个点 $m$ 条边的无向图，经过一个点的代价是进入和离开这个点的两条边的边权的较大... | 难度：普及
题目描述
给出一个 $n$ 个点 $m$ 条边的无向图，经过一个点的代价是进入和离开这个点的两条边的边权的较大值，求从起点 $1$ 到点 $n$ 的最小代价。起点的代价是离开起点的边的边权，终点的代价是进入终点的边的边权。
输入格式
第一行两个数 $n,m$，分别表示点数和边数。
接下来 $m$ 行，每行三个数 $a,b,c$，表示 $a,b$ 之间存在一条长度为 $c$ 的边。
输出格式
一行一个数，表示答案。
样例 #1
样例输入 #1
1
2
3
4
5
6
4 5
1 2 5
1 3 2
2 3 1
2 4 4
3 4 8
样例输出 #1
1
12
数据范围
$1\leq n\leq 10^5$，$1\leq m\leq 2\times 10^5$，$1\leq c\leq 10^6$。
题目分析
1. $Dijkstra$算法的可用性
我们先看看$Dij$算法可不可以直接跑：
从$1$号点开始，先扩展到最近的邻居，此时问题来了，从邻居出发走到下一站的时候会改变从起点走到邻居的费用，这样就不知道第一次该怎么找最优的邻居，不符合$Dijkstra$算法思路。
2.建新图
从$1$号点出发，有一个出发的费用，而经过一个点，也就是从边到边，有另一个费用；从起点到终点，收了边数 + 1次费用。 由此我们可以想到，可以建一个新图，原图中的每条边都可以变成两个点，这两个点可以以该条边的费用双向互通；再加入一个起点、一个终点，新的图就建好了。 但是这样会有一个问题：如果碰到菊花图，那会有$m^2$条新边，这明显不符合题目的数据范围。
3.优化
从一个点出发，从不同的边来到不同的边上费用都不一样，那么恰好，让点的出边排序，这些出边的权值依次上升，权值升高时，路径换了，走到了不同的边。对这些边的权值进行差分处理，升级就建立两边差值的边，降级就建立费用为$0$的边。如果要继续走下去，在这条边上只能换向（也就是再加上这条边的费用），可以发现，到下一个点的时候，（换向后）的边已经是下一个点的出边，在换边的时候，如果换的边费用更低，就走一条费用为$0$的路，如果费用更高，就走一条排序后差分处理的边。
这个时候从$S$点开始跑最短路，由于只有所有出边之间建立了路径，路径的总量约为$2*m$。
AC代码
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int N = 1e5 + 10;
const int U = 4e5 + 10;
const int M = 5e6 + 10;
const ll LL_INF = 0x3f3f3f3f3f3f3f3fLL;
int head[U];
int n, m, s, t;
//新图的边
struct edge{
int to, width, nxt;
}mp[M];
int cnt = 1;
//链式前向星
inline void add_edge(int u, int v, int w) {
mp[cnt] = (edge){v, w, head[u]};
head[u] = cnt++;
}
//老图的点
struct node{
int id, to, width;
bool operator< (const node &x) const {
return x.width > width;
}
};
vector<node> G[N];
bool done[M];
ll dis[M];
inline void dij() {
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
priority_queue<pair<ll, int>> q;
q.push({0, s});
while(!q.empty()) {
int now = q.top().second;
q.pop();
if(done[now]) continue;
done[now] = true;
for(int i = head[now]; i != -1; i = mp[i].nxt) {
int to = mp[i].to;
int w = mp[i].width;
if(dis[to] > dis[now] + w) {
dis[to] = dis[now] + w;
q.push({-dis[to], to});
}
}
}
ll ans = LL_INF;
for(auto i : G[n]) {
ans = min(ans, dis[i.id]);
}
printf("%lld\n", ans);
}
int u, v, w;
int main()
{
scanf("%d%d", &n, &m);
memset(head, -1, sizeof(head));
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &u, &v, &w);
G[u].emplace_back((node){i << 1 | 1, v, w});
G[v].emplace_back((node){i << 1, u, w});
add_edge(i << 1, i << 1 | 1, w);
add_edge(i << 1 | 1, i << 1, w);
}
s = m * 2;
t = m * 2 + 1;
for(auto i : G[1]) {
add_edge(s, i.id, i.width);
}
for(auto i : G[n]) {
add_edge(i.id, t, i.width);
}
for(int i = 1; i <= n; i++) {
sort(G[i].begin(), G[i].end());
int sz = G[i].size();
for(int j = 0; j < sz - 1; j++) {
add_edge(G[i][j].id, G[i][j + 1].id, G[i][j + 1].width - G[i][j].width);
add_edge(G[i][j + 1].id, G[i][j].id, 0);//加边
}
}
dij();
return 0;
}