Submission #138101

#	Time	Username	Problem	Language	Result	Execution time	Memory
138101		rzbt	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	933 ms	30328 KiB

commuter_pass

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 100005
typedef long long ll;

using namespace std;

ll n,m,a,b,x,y;
vector<pair<ll,ll> > niz[MAXN];
vector<ll > preci[MAXN];

set<pair<ll,ll> > q;
ll oda[MAXN],odb[MAXN],odx[MAXN],ody[MAXN],dece[MAXN];
vector<ll> nzm;
ll dpx[MAXN],dpy[MAXN];
ll res;
void dijkstra(ll s,ll *gde){
    q.clear();
    q.insert(mp(0,s));
    while(!q.empty()){
        ll tu=q.begin()->first;
        ll t=q.begin()->second;
        q.erase(q.begin());
        if(gde[t] && t!=s){
            continue;
        }
        gde[t]=tu;
        for(auto x:niz[t]){
            if(!gde[x.first] && x.first!=s){
                q.insert(mp(tu+x.second,x.first));
            }
        }

    }

}



int main()///SVE U LONG LONG
{
    scanf("%lld %lld", &n, &m);
    scanf("%lld %lld", &a, &b);
    scanf("%lld %lld", &x, &y);
    for(ll i=1;i<=m;i++){
        ll t1,t2,t3;
        scanf("%lld %lld %lld", &t1, &t2, &t3);
        niz[t1].pb(mp(t2,t3));
        niz[t2].pb(mp(t1,t3));
    }
    dijkstra(a,oda);
    dijkstra(b,odb);
    dijkstra(x,odx);
    dijkstra(y,ody);
    res=odx[y];
    for(ll i=1;i<=n;i++){
        if(!(oda[i]+odb[i]== oda[b]))continue;

        dpx[i]=odx[i];
        dpy[i]=ody[i];
        for(auto x:niz[i]){
            if(x.second+odb[x.first]+oda[i]==oda[b]){
                dece[i]++;
                preci[x.first].pb(i);
            }
        }
        if(!dece[i])nzm.pb(i);//samo b lol
    }
    while(!nzm.empty()){
        ll t=nzm.back();
        nzm.pop_back();
        res = min(res,min(dpx[t]+ody[t],dpy[t]+odx[t]));
        //printf("  %d      %d %d    %d %d\n",t,dpx[t],odx[t],dpy[t],ody[t]);
        for(auto x:preci[t]){
            dece[x]--;
            if(!dece[x])nzm.pb(x);
            dpx[x]=min(dpx[x],dpx[t]);
            dpy[x]=min(dpy[x],dpy[t]);
        }
    }


    printf("%lld",res);



    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld", &a, &b);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld", &x, &y);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &t1, &t2, &t3);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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