Submission #331782

#	Time	Username	Problem	Language	Result	Execution time	Memory
331782		daniel920712	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	821 ms	46644 KiB

commuter_pass

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <set>
#include <map>
#include <algorithm>
#include <time.h>
#include <algorithm>
#include <queue>
#include <utility>
#include <map>

using namespace std;

vector < pair < long long , pair < long long , long long > > > Next[200005];
vector < long long > Next2[200005];
priority_queue < pair < long long , long long > , vector < pair < long long , long long > > , greater < pair < long long , long long > > > dij;
priority_queue < pair < pair < long long , long long > , long long > , vector < pair < pair < long long , long long > , long long > > , greater < pair < pair < long long , long long > , long long > > > dijj;
queue < long long > ttt;
bool use[200005]={0};
bool have[200005]={0};
long long small[100005]={0};
int main()
{
    //freopen("03-07.txt","rt",stdin);
    long long N,M,S,T,U,V,a,b,c,i,ans=1e18,x;
    scanf("%lld %lld",&N,&M);
    scanf("%lld %lld %lld %lld",&S,&T,&U,&V);
    for(i=1;i<=N;i++) small[i]=-1;
    for(i=0;i<M;i++)
    {
        scanf("%lld %lld %lld",&a,&b,&c);
        Next[a].push_back(make_pair(i,make_pair(b,c)));
        Next[b].push_back(make_pair(i,make_pair(a,c)));
    }
    dij.push(make_pair(0,S));
    while(!dij.empty())
    {
        a=dij.top().first;
        b=dij.top().second;
        dij.pop();
        if(small[b]!=-1) continue;
        small[b]=a;
        for(auto i:Next[b]) dij.push(make_pair(a+i.second.second,i.second.first));

    }
    ttt.push(T);
    while(!ttt.empty())
    {
        i=ttt.front();
        ttt.pop();
        if(have[i]) continue;
        have[i]=1;
        for(auto j:Next[i])
        {
            if(small[i]-j.second.second==small[j.second.first])
            {
                use[j.first]=1;
                ttt.push(j.second.first);
                Next2[j.second.first].push_back(i);
            }
        }

    }

    for(i=1;i<=N;i++) small[i]=-1;
    dijj.push(make_pair(make_pair(0,U),0));
    while(!dijj.empty())
    {
        a=dijj.top().first.first;
        b=dijj.top().first.second;
        x=dijj.top().second;
        dijj.pop();
        if(small[b]!=-1) continue;
        small[b]=a;
        //printf("%lld %lld\n",a,b);
        for(auto i:Next[b])
        {
            if(x==0) dijj.push(make_pair(make_pair(a+i.second.second,i.second.first),0));
            else dijj.push(make_pair(make_pair(a+i.second.second,i.second.first),2));
        }
        if(x==0||x==1) for(auto i:Next2[b]) dijj.push(make_pair(make_pair(a,i),1));

    }
    ans=min(ans,small[V]);

    for(i=1;i<=N;i++) small[i]=-1;
    dijj.push(make_pair(make_pair(0,V),0));
    while(!dijj.empty())
    {
        a=dijj.top().first.first;
        b=dijj.top().first.second;
        x=dijj.top().second;
        dijj.pop();
        if(small[b]!=-1) continue;
        small[b]=a;
        for(auto i:Next[b])
        {
            if(x==0) dijj.push(make_pair(make_pair(a+i.second.second,i.second.first),0));
            else dijj.push(make_pair(make_pair(a+i.second.second,i.second.first),2));
        }
        if(x==0||x==1) for(auto i:Next2[b]) dijj.push(make_pair(make_pair(a,i),1));

    }
    ans=min(ans,small[U]);


    printf("%lld\n",ans);

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |     scanf("%lld %lld",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |     scanf("%lld %lld %lld %lld",&S,&T,&U,&V);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |         scanf("%lld %lld %lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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