Submission #108786

#	Time	Username	Problem	Language	Result	Execution time	Memory
108786		thebes	Commuter Pass (JOI18_commuter_pass)	C++14	16 / 100	2033 ms	23280 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

const int MN = 1e5+5;
typedef long long ll;
typedef pair<ll,ll> pii;
ll d[MN], A[MN], B[MN], a[MN], b[MN], n, m, s, t, u, v, i, x, y, w, st[MN], cnt[MN];
struct pq{bool operator()(const pii&i,const pii&j){return i.second>j.second;}};
priority_queue<pii,vector<pii>,pq>q; vector<pair<ll,ll>> adj[MN];

int main(){
    scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&s,&t,&u,&v);
    for(i=1;i<=m;i++){
        scanf("%lld%lld%lld",&x,&y,&w);
        adj[x].push_back({y,w});
        adj[y].push_back({x,w});
    }
    memset(a,0x3f,sizeof(a));
    memset(b,0x3f,sizeof(b));
    memset(d,0x3f,sizeof(d));
    memset(A,0x3f,sizeof(A));
    memset(B,0x3f,sizeof(B));
    q.push({u,0}); st[u]=cnt[u]=1; a[u]=0;
    while(q.size()){
        ll nd = q.top().first; q.pop();
        cnt[nd]--;
        if(!st[nd]) continue;
        else st[nd]=0;
        for(auto v : adj[nd]){
            if(a[nd]+v.second<a[v.first]){
                st[v.first]=1;
                a[v.first]=a[nd]+v.second;
                if(!cnt[v.first]){cnt[v.first]++; q.push({v.first,a[v.first]});}
            }
        }
    }
    memset(st,0,sizeof(st));
    memset(cnt,0,sizeof(cnt));
    q.push({v,0}); st[v]=cnt[v]=1; b[v]=0;
    while(q.size()){
        ll nd = q.top().first; q.pop();
        cnt[nd]--;
        if(!st[nd]) continue;
        else st[nd]=0;
        for(auto v : adj[nd]){
            if(b[nd]+v.second<b[v.first]){
                st[v.first]=1;
                b[v.first]=b[nd]+v.second;
                if(!cnt[v.first]){cnt[v.first]++; q.push({v.first,b[v.first]});}
            }
        }
    }
    memset(st,0,sizeof(st));
    memset(cnt,0,sizeof(cnt));
    q.push({s,0}); st[s]=cnt[s]=1; d[s]=0; A[s]=a[s]; B[s]=b[s];
    while(q.size()){
        ll nd = q.top().first; q.pop();
        cnt[nd]--;
        if(!st[nd]) continue;
        else st[nd]=0;
        for(auto v : adj[nd]){
            if(d[nd]+v.second<d[v.first]){
                st[v.first]=1;
                d[v.first]=d[nd]+v.second;
                A[v.first]=min(a[v.first],A[nd]);
                B[v.first]=min(b[v.first],B[nd]);
                if(!cnt[v.first]){cnt[v.first]++; q.push({v.first,d[v.first]});}
            }
            else if(d[nd]+v.second==d[v.first]&&A[nd]+B[nd]<A[v.first]+B[v.first]){
                st[v.first]=1;
                A[v.first]=A[nd];
                B[v.first]=B[nd];
                if(!cnt[v.first]){cnt[v.first]++; q.push({v.first,d[v.first]});}
            }
        }
    }
    printf("%lld\n",min(a[v],A[t]+B[t]));
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&s,&t,&u,&v);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld",&x,&y,&w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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