P11938

Rnfcr · 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;
}