题目描述
给出一个 n 个点 m 条边的无向图，经过一个点的代价是进入和离开这个点的两条边的边权的较大值，求从起点 1 到点 n 的最小代价。起点的代价是离开起点的边的边权，终点的代价是进入终点的边的边权。
输入格式
第一行两个数 n,m，分别表示点数和边数。
接下来 m 行，每行三个数 a,b,c，表示 a,b 之间存在一条长度为 c 的边。
输出格式
一行一个数，表示答案。
样例 #1
样例输入 #1
4 5
1 2 5
1 3 2
2 3 1
2 4 4
3 4 8
样例输出 #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代码
#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;
}
