脚本宝典收集整理的这篇文章主要介绍了【题解】[JOI2018] Commuter Pass，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

比较套路的题目。

首先我们需要求出 (Sto T) 的最短路可行边。

我们分别以 (S/T) 为起点，跑最短路得到 (dist_1,dist_2) ，如果两端 (dist) 之和加上边的长度为最短路，则当前边出现在一条最短路中。

现在从 (Uto V) ，免费的一定是一条连续的路径。

而这条免费的路径要么是顺着最短路径图走一段，要么是逆着最短路径图走一段，而不能同时有顺向或逆向走。

简单想了一个贪心，大概是先求出 (U/V) 到最短路径图的最近点 (P,Q)，再从 (P/Q) 为起点出发顺向或逆向找到最近公共可达点，分别以 (P,Q) 为起点正图反图都跑一遍最短路。

码了 (10) 分钟感觉太麻烦了，不如直接分层图。第 (1) 层和第 (4) 层分别表示还未开始免费路径，已经结束免费路径。第 (2) 层表示免费路径顺着走，这一层就是最短路图，第 (3) 层表示免费路径逆着走，就是最短路图的反图。

最后再跑一遍最短路即可，一共跑三遍最短路，@R_410_1304@ (mathcal{O}((N+M)LOG (N+M)))。

#include<bITs/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define PRe(i,a,b) for(int i=a;i>=b;i--)
#define N 400005
#define int long long 
using namespace std;
int n,m,d[N],c[N],mk[N],h[N],tot,s,t,u,v;
struct Edge{int to,nxt,val;}e[N];
void add(int x,int y,int z){e[++tot].nxt=h[x];h[x]=tot;e[tot].to=y;e[tot].val=z;}
tyPEdef pair<int,int> Pr;
priority_queue<pair<int,int>>q;
vector<Pr>a[N];
void ins(int x,int y,int z){a[x].push_back(make_pair(y,z));}
void dij(){
	memset(d,0x3f,sizeof(d));
	d[s]=0;q.push(make_pair(0,s));
	while(!q.empty()){
		int x=q.top().second;q.pop();mk[x]=1;
		for(int i=h[x];i;i=e[i].nxt)if(d[x]+e[i].val<d[e[i].to])
			d[e[i].to]=d[x]+e[i].val,q.push(make_pair(-d[e[i].to],e[i].to));
		while(!q.empty()&&mk[q.top().second])q.pop();
	}
	memset(c,0x3f,sizeof(c));
	memset(mk,0,sizeof(mk));
	c[t]=0;q.push(make_pair(0,t));
	while(!q.empty()){
		int x=q.top().second;q.pop();mk[x]=1;
		for(int i=h[x];i;i=e[i].nxt)if(c[x]+e[i].val<c[e[i].to])
			c[e[i].to]=c[x]+e[i].val,q.push(make_pair(-c[e[i].to],e[i].to));
		while(!q.empty()&amp;&mk[q.top().second])q.pop();
	}
	rep(x,1,n)
		for(int i=h[x];i;i=e[i].nxt)
			if(d[x]+e[i].val+c[e[i].to]==d[t]){
				ins(x+n,e[i].to+n,0),ins(e[i].to+n+n,x+n+n,0);
			}
}
void solve(){
	memset(d,0x3f,sizeof(d));
	memset(mk,0,sizeof(mk));
	d[u]=0;q.push(make_pair(0,u));
	while(!q.empty()){
		int x=q.top().second;q.pop();mk[x]=1;
		for(auto w:a[x]){
			int y = w.First,z = w.second;
			if(d[x] + z < d[y])d[y] = d[x] + z,q.push(make_pair(-d[y],y));
		}
		while(!q.empty()&&mk[q.top().second])q.pop();
	}
	printf("%lldn",d[v+n+n+n]);
}
signed main(){
	scanf("%lld%lld",&n,&m);
	scanf("%lld%lld%lld%lld",&s,&t,&u,&v);
	rep(i,1,m){
		int x,y,z;scanf("%lld%lld%lld",&x,&y,&z);
		add(x,y,z);add(y,x,z);
		ins(x,y,z);ins(y,x,z);
		ins(x+n+n+n,y+n+n+n,z);ins(y+n+n+n,x+n+n+n,z);
	}
	rep(i,1,n)ins(i,i+n,0),ins(i,i+n+n,0),ins(i+n,i+n+n+n,0),ins(i+n+n,i+n+n+n,0);
	dij();solve();
	return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的【题解】[JOI2018] Commuter Pass全部内容，希望文章能够帮你解决【题解】[JOI2018] Commuter Pass所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。