Submission #632683

#	Time	Username	Problem	Language	Result	Execution time	Memory
632683		Iwanttobreakfree	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	428 ms	29136 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define int long long
#define pii pair<int,int>
int par(int a,vector<int>& id){
    if(id[a]==a)return a;
    return id[a]=par(id[a],id);
}
void unite(int a,int b,vector<int>& id){
    a=par(a,id),b=par(b,id);
    id[a]=b;
}
void nodijkstra(int a,int b,vector<vector<pii>>& p,vector<int>& dist,vector<int>& distu,vector<int>& distv,int s,int t){
    queue<int> q;
    vector<vector<int>> g(p.size(),vector<int>());
    q.push(a);
    vector<bool> seen(g.size(),false);
    while(!q.empty()){
        int u=q.front();
        seen[u]=true;
        q.pop();
        for(auto v:p[u]){
            if(dist[v.first]+v.second==dist[u]){
                g[u].push_back(v.first);
                if(!seen[v.first])q.push(v.first);
            }
        }
    }
    int ans=distu[t],n=g.size();
    vector<int> bestu(n),bestv(n),cnt(n),cnt2(n);
    for(int i=0;i<n;i++)for(auto v:g[i]){
        cnt[v]++;
        cnt2[v]++;
    }
    for(int i=0;i<n;i++){
        bestu[i]=distu[i];
        bestv[i]=distv[i];
    }
    q.push(a);
    while(!q.empty()){
        int u=q.front();
        //cout<<u<<' ';
        ans=min(ans,bestu[u]+distv[u]);
        q.pop();
        for(auto v:g[u]){
            cnt[v]--;
            bestu[v]=min(bestu[v],bestu[u]);
            if(!cnt[v])q.push(v);
        }
    }
    q.push(a);
    while(!q.empty()){
        int u=q.front();
        ans=min(ans,bestv[u]+distu[u]);
        q.pop();
        for(auto v:g[u]){
            cnt2[v]--;
            bestv[v]=min(bestv[v],bestv[u]);
            if(!cnt2[v])q.push(v);
        }
    }
    cout<<ans<<'\n';
}
void dijkstra2(int s,int t,vector<vector<pii>>& g,int a,int b,vector<int>& dist){
    priority_queue<pii> pqu,pqv;
    vector<int> distu(g.size(),1e18),distv(g.size(),1e18);
    pqu.push({0,s});
    distu[s]=0;
    while(!pqu.empty()){
        int u=pqu.top().second,d=-pqu.top().first;
        pqu.pop();
        if(d>distu[u])continue;
        for(auto v:g[u]){
            if(distu[v.first]>distu[u]+v.second){
                distu[v.first]=distu[u]+v.second;
                pqu.push({-distu[v.first],v.first});
            }
        }
    }
    pqv.push({0,t});
    distv[t]=0;
    while(!pqv.empty()){
        int u=pqv.top().second,d=-pqv.top().first;
        pqv.pop();
        if(d>distv[u])continue;
        for(auto v:g[u]){
            if(distv[v.first]>distv[u]+v.second){
                distv[v.first]=distv[u]+v.second;
                pqv.push({-distv[v.first],v.first});
            }
        }
    }
    int ans=1e18,n=g.size();
    //vector<pii> distid(n,{1e18,1e18});
    nodijkstra(b,a,g,dist,distu,distv,s,t);
    /*for(int i=0;i<n;i++){
        cout<<id[i]<<' ';
        ans=min(ans,distid[i].first+distid[i].second);
    }
    cout<<ans<<'\n';*/
}
void dijkstra(int a,int b,vector<vector<pii>>& g,int s,int t){
    priority_queue<pii> pq;
    vector<int> dist(g.size(),1e18);
    pq.push({0,a});
    dist[a]=0;
    while(!pq.empty()){
        int u=pq.top().second,d=-pq.top().first;
        pq.pop();
        if(d>dist[u])continue;
        for(auto v:g[u]){
            if(dist[v.first]>dist[u]+v.second){
                dist[v.first]=dist[u]+v.second;
                pq.push({-dist[v.first],v.first});
            }
        }
    }
    //vector<int> id=nodijkstra(b,a,g,dist);
    //for(int i=0;i<g.size();i++)cout<<id[i]<<' ';
    dijkstra2(s,t,g,a,b,dist);
}
signed main(){
    int n,m,u,v,s,t,x,y,w;
    cin>>n>>m>>s>>t>>u>>v;
    s--;t--;u--;v--;
    vector<vector<pii>> g(n,vector<pii>());
    while(m--){
        cin>>x>>y>>w;
        x--;y--;
        g[x].push_back({y,w});
        g[y].push_back({x,w});
    }
    dijkstra(s,t,g,u,v);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra2(long long int, long long int, std::vector<std::vector<std::pair<long long int, long long int> > >&, long long int, long long int, std::vector<long long int>&)':
commuter_pass.cpp:95:9: warning: unused variable 'ans' [-Wunused-variable]
   95 |     int ans=1e18,n=g.size();
      |         ^~~
commuter_pass.cpp:95:18: warning: unused variable 'n' [-Wunused-variable]
   95 |     int ans=1e18,n=g.size();
      |                  ^

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