自动搬运

查看原文

来自洛谷，原作者为

	Rnfcr 这个家伙很懒，什么也没留下

搬运于2025-08-24 23:11:29，当前版本为作者最后更新于2025-03-24 21:27:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

因为每走一条边要换一张图，考虑使用分层图来解决这个问题。将 $G_1$ 中的每条边 $(u_i,v_i)$ 转化为 $(u_i,v_i+n)$ 的一条边，$G_2$ 中的 $(u_i,v_i)$ 转化为 $(u_i+n,v_i)$ 来解决移动次数奇偶性的问题，之后在 $G_1$ 和 $G_2$ 上分别跑一次 dijkstra，求出哪些点对间是可达的，之后就是求从 $s$ 点到 $t$ 点或 $t+n$ 点的最长路了。无解有从 $s$ 点可以到达一个环和 $s$ 点与 $t$ 或 $t+n$ 点不连通两种情况，用 SPFA 算法求最长路即可。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n,s,t,m1,m2;
struct edge{
	int v,w;
};
vector<edge> ve[2009],G1[2009],G2[2009];
int dis[2009],cnt[2009],vis[2009],f[2009],ff[2009];
deque<int> q;
bool check(int u,int v){
	if(u<=n){//G1->G1
		if(f[u]>f[v-n]) return 1;
		return 0;
	}
	else{//G2->G2
		if(f[u]>f[v+n]) return 1;
		return 0;
	}
}
bool SPFA(int st){
	for(int i=1;i<=2*n;i++) dis[i]=1e18;
	dis[st]=0;
	vis[st]=1;
	q.push_back(st);
	while(!q.empty()){
		int u=q.front();
		vis[u]=0;
		q.pop_front();
		for(int i=0;i<ve[u].size();i++){
			edge now=ve[u][i];
			int v=now.v,w=now.w;
			if(!check(u,v)) continue;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>=2*n) return 1;
				if(!vis[v]){
					vis[v]=1;
					if(!q.empty()&&dis[v]>dis[q.front()]) q.push_back(v);
					else q.push_front(v);
				}
			}
		}
	}
	return 0;
}
struct data{
    int v,w;
};
priority_queue<data> q2;
bool operator < (data a,data b){
    return a.w>b.w;
}
void dij(int st){
	for(int i=1;i<=n;i++) f[i]=1e18;
	f[st]=0;
	q2.push(data {st,0});
    while(!q2.empty()){
        int v=q2.top().v;
        int w=q2.top().w;
        if(v>n) continue;
        q2.pop();
        if(vis[v]) continue;
        vis[v]=1;
        f[v]=w;
        for(int i=0;i<G1[v].size();i++){
            if(!vis[G1[v][i].v]&&w+G1[v][i].w<f[G1[v][i].v]){
            	f[G1[v][i].v]=w+G1[v][i].w;
            	q2.push(data {G1[v][i].v,w+G1[v][i].w});
			}
        }
    }
}
void dij1(int st){
	for(int i=n+1;i<=n+n;i++) f[i]=1e18;
	f[st]=0;
	q2.push(data {st,0});
    while(!q2.empty()){
        int v=q2.top().v;
        int w=q2.top().w;
        if(v<=n) continue;
        q2.pop();
        if(vis[v]) continue;
        vis[v]=1;
        f[v]=w;
        for(int i=0;i<G2[v].size();i++){
            if(!vis[G2[v][i].v]&&w+G2[v][i].w<f[G2[v][i].v]){
            	f[G2[v][i].v]=w+G2[v][i].w;
            	q2.push(data {G2[v][i].v,w+G2[v][i].w});
			}
        }
    }
}
signed main(){
    ios::sync_with_stdio(NULL),cin.tie(0),cout.tie(0);
   	cin>>n>>s>>t;
   	cin>>m1;
   	for(int i=1;i<=m1;i++){
   		int u,v,w;
   		cin>>u>>v>>w;
   		w*=-1;
   		ve[u].push_back(edge{v+n,w});
    	ve[v].push_back(edge{u+n,w});
    	G1[u].push_back(edge{v,-w});
    	G1[v].push_back(edge{u,-w});
	}
	cin>>m2;
   	for(int i=1;i<=m2;i++){
   		int u,v,w;
   		cin>>u>>v>>w;
   		w*=-1;
   		ve[u+n].push_back(edge{v,w});
    	ve[v+n].push_back(edge{u,w});
    	G2[u+n].push_back(edge{v+n,-w});
    	G2[v+n].push_back(edge{u+n,-w});
	}
	dij(t);
	dij1(t+n);
	memset(vis,0,sizeof(vis));
	if(SPFA(s)){
		cout<<-1;
		return 0;
	}
	else{
		cout<<min(dis[t],dis[n+t])*-1;
	}
    return 0;
}