#C231107C. 最短路(path)

前言（Front talk)

没学过的算法呢~开心ヾ(≧▽≦*)o

网址（Website）

题目详情 - 最短路(path) - Super

题解 - 最短路(path) - Super

题目（Problem）

给定一个个点条边的无向图，求上到其他点的“最短路”的长度。

对于“最短路”的定义，假设一条路径上的边权依次为，定义为路径长度，求出在这个定义下的最短路。

范围： 对的数据：；；。数据保证不存在自环。

题解（Solution）

为什么这个题解的形容这么，令人误解。

该题文字有误，题解代码却是对的。

由于题解代码太丑了，所以我用了 cx 大佬的代码，cx太强了，膜膜膜。

修改后的题解（Repaired Solution）

代价的形式中对最大值和最小值的要求比较难处理, 无法记录到最短路中直接计算,但可以将最大最小边均改成任意, 即等价于对于每条路径可以选一条边免费, 选一条边计算两次, 问最短路。这样我们最优解一定是在某条路径上最大边免费, 最小边计算两次, 否则更劣。

那么这样就可以求分层图最短路了, 改为求到的最短路, 对每条边, 连到权值为，到权值为，到权值为即可。

代码（Code）

我的代码（五层图）

第一层是原图；

第二、三层是先取后取；

第四、五层是先去后取。

#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的代码（四层图）

cx大佬 的博客网址： Huasushis ‘s Blog

其实就是：代表跳层，代表跳层。

#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;
}