【经典例题】P6822 [PA2012] Tax

考虑边拆成点。然后经过这些点的路径就是答案的路径。

考虑直接起点，终点连边。

然后我们考虑转移两条出边入边的过程。是 \((a, b) \to (b, c)\) 考虑到反向边是一致的所以可以 \((b, a) \to (b, c)\)。这个启发我们反向边之间可以连一条 \(w\) 的边。

然后我们考虑按 w 排序，然后 \(i \to i + 1\) 连一个差值，\(i + 1 \to i\) 连一个 0 边就做完了。

我们发现取我们可以在一个点中不断转移差值，这个就是取 max 的过程，然后通过反向边走出去，这个建图真的牛子的。

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
#define pb push_back
#define lc u << 1
#define rc u << 1 | 1
#define int long long

using namespace std;

const int _ = 1e5 + 5, __ = 2e5 + 5, mod = 1e9 + 7;

int n, m, dis[__], s = 0, t = 1;

struct EDGE { 
	int v, w, id; 
	bool operator < (const EDGE & x) const { return w < x.w; }
} ;
vector <EDGE> e[_], g[_];
void adde (int u, int v, int w, int id) { e[u].pb({v, w, id}); }
void addg (int u, int v, int w) { g[u].pb({v, w, 114514}); }

struct node {
	int u, d;
	bool operator < (const node & x) const { return d > x.d; }
} ;
priority_queue <node> q;

void dijkstra (int st, int ed) {
	memset(dis, 0x3f, sizeof(dis)), dis[st] = 0;
	q.push({st, 0});
	while (! q.empty()) {
		int u = q.top().u, d = q.top().d;
		q.pop(); if (d != dis[u]) continue ; 
		for (auto & [v, w, id] : g[u]) 
			if (dis[v] > d + w)	dis[v] = d + w, q.push({v, dis[v]});
	}
	cout << dis[ed]; return ;
}
signed main () {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	ios :: sync_with_stdio(0);
 	cin >> n >> m;
 	rep(i, 1, m) {
 		int u, v, w;
 		cin >> u >> v >> w;
 		adde(u, v, w, i << 1), adde(v, u, w, i << 1 | 1);
	}
	rep(u, 1, n) {
		if (e[u].empty()) continue ;
		sort(e[u].begin(), e[u].end());
		for (auto & [v, w, id] : e[u]) {
			addg(id, id ^ 1, w);
			if (u == 1) addg(s, id, w);
			if (v == n) addg(id, t, w);
		}
		auto it = e[u].begin();
		for (++ it; it != e[u].end(); it ++) {
			auto prv = (it - 1);
			addg(it -> id, prv -> id, 0), addg(prv -> id, it -> id, it -> w - prv -> w);
		}
	}
	dijkstra(s, t);
	return 0;
}