Submission #477147

#	Time	Username	Problem	Language	Result	Execution time	Memory
477147		Qw3rTy	Commuter Pass (JOI18_commuter_pass)	C++11	100 / 100	1303 ms	112540 KiB

commuter_pass

/*
 * Key Observation: 只能顺着S->T走一段免费的或者逆着S->T走一段免费的; 不可能顺着+逆着，否则这一定不是S->T的最短路的一部分
 */
#include <bits/stdc++.h>
#define int long long
#define INF 1e16
#define pi pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int maxN = 2e5+5;
struct cmp{
    bool operator() (pi a, pi b){
        return a.fi > b.fi;
    }
};
int N,M,S,T,U,V,res;
vector<pi> adj[maxN]; //original graph
vector<pi> adj2[maxN<<2]; //4-layered graph
int distS[maxN],distT[maxN];
void dijk(int dist[], int src){
    for(int i = 1; i <= N; ++i)dist[i] = INF;
    bool vis[maxN];
    memset(vis,false,sizeof(vis));
    priority_queue<pi,vector<pi>,cmp> Q;
    Q.push(pi(0,src));
    dist[src] = 0;
    while(!Q.empty()){
        pi p = Q.top(); Q.pop();
        int d = p.fi; int loc = p.se;
        if(vis[loc])continue;
        vis[loc] = true;
        for(auto x: adj[loc]){
            if(dist[loc] + x.se < dist[x.fi]){
                dist[x.fi] = dist[loc] + x.se;
                if(!vis[x.fi]){
                    Q.push(pi(dist[x.fi],x.fi));
                }
            }
        }
    }
}
//for dijkstra on the layered graph
int dist[maxN<<2];
bool vis[maxN<<2];
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("../test.in","r",stdin);
    cin >> N >> M >> S >> T >> U >> V;
    for(int i = 1; i <= M; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].pb(pi(b,c));
        adj[b].pb(pi(a,c));
        //layer 1 to layer 1
        adj2[a].pb(pi(b,c));
        adj2[b].pb(pi(a,c));
        //layer 1 to layer 2, enter into forward commuter pass (S->T)
        adj2[a].pb(pi(N+a,0));
        adj2[b].pb(pi(N+b,0));
        //layer 1 to layer 3, enter into backward commuter pass (T->S)
        adj2[a].pb(pi(2*N+a,0));
        adj2[b].pb(pi(2*N+b,0));
        //layer 1 to layer 4, for skipping commuter pass
        adj2[a].pb(pi(3*N+a,0));
        adj2[b].pb(pi(3*N+b,0));
        //layer 2 to layer 4, exiting commuter pass
        adj2[N+i].pb(pi(3*N+i,0));
        //layer 3 to layer 4, exiting commuter pass
        adj2[2*N+i].pb(pi(3*N+i,0));
        //layer 4 to layer 4
        adj2[3*N+a].pb(pi(3*N+b,c));
        adj2[3*N+b].pb(pi(3*N+a,c));
    }
    dijk(distS,S);
    dijk(distT,T);
    for(int i = 1; i <= N; ++i){
        for(auto x: adj[i]){
            if(distS[i] + x.se + distT[x.fi] == distS[T]){
                //Ensures edge x is a part of a shortest path from S to T
                //this edge must be from S->T and not T->S
                //layer 2 to layer 2
                adj2[N+i].pb(pi(N+x.fi,0));
                //layer 3 to layer 3
                adj2[2*N+x.fi].pb(pi(2*N+i,0));
            }
        }
    }
    //dijk for adj2, src = U
    for(int i = 1; i <= 4*N; ++i)dist[i] = INF;
    memset(vis,false,sizeof(vis));
    priority_queue<pi,vector<pi>,cmp> Q;
    Q.push(pi(0,U));
    dist[U] = 0;
    while(!Q.empty()){
        pi p = Q.top(); Q.pop();
        int loc = p.se;
        if(vis[loc])continue;
        vis[loc] = true;
        for(auto x: adj2[loc]){
            if(dist[loc] + x.se < dist[x.fi]){
                dist[x.fi] = dist[loc] + x.se;
                if(!vis[x.fi]){
                    Q.push(pi(dist[x.fi],x.fi));
                }
            }
        }
    }
    cout << dist[3*N+V] << '\n';
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijk(long long int*, long long int)':
commuter_pass.cpp:31:13: warning: unused variable 'd' [-Wunused-variable]
   31 |         int d = p.fi; int loc = p.se;
      |             ^

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45