Submission #477134

#	Time	Username	Problem	Language	Result	Execution time	Memory
477134		Qw3rTy	Commuter Pass (JOI18_commuter_pass)	C++11	31 / 100	554 ms	22536 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 = 1e5+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];
int distS[maxN],distS2[maxN],distT[maxN],distT2[maxN],distU[maxN],distV[maxN],dpU[maxN],dpV[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));
                }
            }
        }
    }
}
void dijk2(int dist[], int src, int end){
    for(int i = 1; i <= N; ++i)dist[i] = INF;
    bool vis[maxN];
    memset(vis,false,sizeof(vis));
    for(int i = 1; i <= N; ++i)dpU[i] = dpV[i] = INF;
    priority_queue<pi,vector<pi>,cmp> Q;
    Q.push(pi(0,src));
    dist[src] = 0;
    dpU[src] = distU[src];
    dpV[src] = distV[src];
    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));
                }
            }
            if(distS[x.fi] + distT[x.fi] == distS[T]){
                //There must be a shortest path from S to T that passes thru x.fi if the above is satisfied
                dpU[x.fi] = min(dpU[x.fi],min(dpU[loc],distU[x.fi]));
                dpV[x.fi] = min(dpV[x.fi],min(dpV[loc],distV[x.fi]));
            }
        }
    }
    res = min(res,dpU[end]+dpV[end]);
}
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));
    }
    dijk(distU,U);
    dijk(distV,V);
    dijk(distS,S);
    dijk(distT,T);
    res = distU[V]; //Min dist without commuter pass
    dijk2(distS2,S,T);
    dijk2(distT2,T,S);
    cout << res << '\n';
}

Compilation message (stderr)

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

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