#C231107C. 最短路(path)
标签（Label）
- 分层图
- 最短路算法
网址（Website）
题目（Problem）
给定一个 $n$ 个点 $m$ 条边的无向图 $G$，求 $G$ 上 $1$ 到其他点的“最短路”的长度。
对于“最短路”的定义，假设一条路径上的边权依次为 $w_{1}, w_{2}, \ldots w_{k}$，定义 $S(w)=\min(w_{i})-\max(w_{i})+\sum w_{i}$ 为路径长度，求出在这个定义下的最短路。
范围： 对 $100 %$ 的数据：$n, m \leq 2 \times 10^{5}$；$1 \leq u, v \leq n$；$0<w \leq 10^{9}$。数据保证不存在自环。
题解（Solution）
$\qquad$为什么这个题解的形容这么，令人误解。
$\qquad$该题文字有误，题解代码却是对的。
$\qquad$由于题解代码太丑了，所以我用了 cx 大佬的代码，cx太强了，膜膜膜。
修改后的题解（Repaired Solution）
$\qquad$代价的形式中对最大值和最小值的要求比较难处理, 无法记录到最短路中直接计算,但可以将最大最小边均改成任意, 即等价于对于每条路径可以选一条边免费, 选一条边计算两次, 问最短路。这样我们最优解一定是在某条路径上最大边免费, 最小边计算两次, 否则更劣。
$\qquad$那么这样就可以求分层图最短路了, 改为求 $(1,0)$ 到 $(i, 2)$ 的最短路, 对每条边 $(u,v, w)$, 连 $(u, k)$ 到 $(v, k)$ 权值为 $w$ ，$(u,0)$ 到 $(v, 1)$ 权值为 $2w$，$(u,1)$ 到 $(v,2)$ 权值为 $0$ 即可。
代码（Code）
我的代码（五层图）
$\qquad$第一层是原图；
$\qquad$第二、三层是先取 $min$ 后取 $max$ ；
$\qquad$第四、五层是先去 $max$ 后取 $min$ 。
#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
#define P pair<int,int>
inline int input(){int x1;return cin>>x1,x1;}
const int N = 1012345;
vector<P> ft[N];
int n,m;
priority_queue<P> q;
int d[N];
void dijkstra(int root){
q.push({0,root}),d[root]=0;
while(q.size()){
int x=q.top().second;q.pop();
for(auto p:ft[x]){
int y=p.first,w=p.second;
if(d[x]+w<d[y]){
d[y]=d[x]+w;
q.push({-d[y],y});
}
}
}
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
string str("path");
freopen((str+".in").c_str(),"r",stdin);
freopen((str+".out").c_str(),"w",stdout);
cin>>n>>m;For(i,1,m){
int x1=input(),y1=input(),v=input();//第一层
int x2=x1+n,y2=y1+n;//第二层
int x3=x2+n,y3=y2+n;//第三层
int x4=x3+n,y4=y3+n;//第四层
int x5=x4+n,y5=y4+n;//第五层
//层内建点
ft[x1].push_back({y1,v});
ft[y1].push_back({x1,v});
ft[x2].push_back({y2,v});
ft[y2].push_back({x2,v});
ft[x3].push_back({y3,v});
ft[y3].push_back({x3,v});
ft[x4].push_back({y4,v});
ft[y4].push_back({x4,v});
ft[x5].push_back({y5,v});
ft[y5].push_back({x5,v});
//跨层建点
ft[x1].push_back({y2,v*2});
ft[y1].push_back({x2,v*2});
ft[x2].push_back({y3,0});
ft[y2].push_back({x3,0});
ft[x1].push_back({y4,0});
ft[y1].push_back({x4,0});
ft[x4].push_back({y5,v*2});
ft[y4].push_back({x5,v*2});
}
memset(d,0x3f,sizeof(d));
dijkstra(1);
For(x,2,n) cout<<min({d[x],d[x+2*n],d[x+4*n]})<<' ';cout<<'\n';
return 0;
}cx的代码（四层图）
$\qquad$cx大佬 的博客网址： Huasushis ‘s Blog
$\qquad$其实就是： $min$ 代表跳 $1$ 层， $max$ 代表跳 $2$ 层。
#include <bits/stdc++.h>
#define int long long
#define N 200010
using namespace std;
int n, m;
int u, v, c;
int first[N * 3], nxt[N * 5], to[N * 5], w[N * 5], et;
void add(int u, int v, int c) {
nxt[++et] = first[u];
first[u] = et;
to[et] = v;
w[et] = c;
}
int dis[N][4];
#define pii pair<int, int>
#define piii pair<int, pii>
#define fi first
#define se second
#define mp make_pair
#define inf 0x3f3f3f3f
bool vis[N][4];
void dij() {
memset(dis, 0x3f, sizeof(dis));
priority_queue<piii, vector<piii>, greater<piii>> q;
dis[1][0] = 0;
q.emplace(0, mp(1, 0));
while (!q.empty()) {
int u = q.top().se.fi;
int s = q.top().se.se;
q.pop();
if (vis[u][s]) continue;
vis[u][s] = 1;
for (int i = first[u]; i; i = nxt[i]) {
if (!(s & 1)) {//0-->1 2-->3 (走min)
if (dis[to[i]][s | 1] > dis[u][s] + w[i] * 2) {
dis[to[i]][s | 1] = dis[u][s] + w[i] * 2;
q.emplace(dis[to[i]][s | 1], mp(to[i], s | 1));
}
}
if (!(s & 2)) {//0-->2 1-->3 (走max)
if (dis[to[i]][s | 2] > dis[u][s]) {
dis[to[i]][s | 2] = dis[u][s];
q.emplace(dis[to[i]][s | 2], mp(to[i], s | 2));
}
}
if (!s) {//0-->3 (走普通边到3)
if (dis[to[i]][3] > dis[u][s] + w[i]) {
dis[to[i]][3] = dis[u][s] + w[i];
}
}
if (dis[to[i]][s] > dis[u][s] + w[i]) {//0-->0 1-->1 2-->2 3-->3(在当前层走普通边)
dis[to[i]][s] = dis[u][s] + w[i];
q.emplace(dis[to[i]][s], mp(to[i], s));
}
}
}
}
signed main() {
freopen("path.in", "r", stdin);
freopen("path.out", "w", stdout);
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= m; ++i) {
scanf("%lld%lld%lld", &u, &v, &c);
add(u, v, c);
add(v, u, c);
}
dij();
for (int i = 2; i <= n; ++i) printf("%lld ", dis[i][3]);
return 0;
}
