Submission #1226605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226605		wedonttalkanymore	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	2096 ms	327680 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m,S,T,U,V;
    cin>>n>>m>>S>>T>>U>>V;
    vector<int>a(m),b(m),c(m);
    vector<vector<pair<int,int>>> adj(n+1);
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i]>>c[i];
        adj[a[i]].emplace_back(b[i],c[i]);
        adj[b[i]].emplace_back(a[i],c[i]);
    }
    vector<ll> dist_s(n+1,INF), dist_t(n+1,INF);
    auto dijkstra=[&](int src, vector<ll>& dist){
        dist.assign(n+1,INF);
        dist[src]=0;
        priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
        pq.push({0,src});
        while(!pq.empty()){
            auto [d,u]=pq.top(); pq.pop();
            if(d>dist[u]) continue;
            for(auto [v,w]:adj[u]) if(dist[v]>d+w){
                dist[v]=d+w;
                pq.push({dist[v],v});
            }
        }
    };
    dijkstra(S,dist_s);
    dijkstra(T,dist_t);
    map<pair<int,int>,ll> mp_cost;
    map<pair<int,int>,int> mp_id;
    int K=0;
    for(int i=0;i<m;i++){
        int u=a[i], v=b[i];
        int x=min(u,v), y=max(u,v);
        if((dist_s[u]+c[i]+dist_t[v]==dist_s[T])||(dist_s[v]+c[i]+dist_t[u]==dist_s[T])){
            mp_cost[{x,y}]=0;
            mp_id[{x,y}]=++K;
        } else {
            mp_cost[{x,y}]=c[i];
            mp_id[{x,y}]=0;
        }
    }
    vector<vector<ll>> dist_ans(n+1, vector<ll>(K+1,INF));
    using State = tuple<ll,int,int>;
    priority_queue<State,vector<State>,greater<State>> pq;
    dist_ans[U][0]=0;
    pq.push({0,U,0});
    while(!pq.empty()){
        auto [d,u,pid]=pq.top(); pq.pop();
        if(d>dist_ans[u][pid]) continue;
        for(auto [v,_w]:adj[u]){
            int x=min(u,v), y=max(u,v);
            ll w = mp_cost[{x,y}];
            int eid = mp_id[{x,y}];
            if(w>0){
                if(d+w<dist_ans[v][pid]){
                    dist_ans[v][pid]=d+w;
                    pq.push({dist_ans[v][pid],v,pid});
                }
            } else {
                int next_pid = pid;
                if(pid==0) next_pid=eid;
                else if(pid!=eid) continue;
                if(d<dist_ans[v][next_pid]){
                    dist_ans[v][next_pid]=d;
                    pq.push({d,v,next_pid});
                }
            }
        }
    }
    ll ans=INF;
    for(int pid=0;pid<=K;pid++) ans=min(ans,dist_ans[V][pid]);
    cout<<ans;
    return 0;
}

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