Submission #331780

#	Time	Username	Problem	Language	Result	Execution time	Memory
331780		daniel920712	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	590 ms	34648 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;
queue < long long > ttt;
bool use[200005]={0};
bool have[200005]={0};
long long small[100005]={0};
int main()
{
    long long N,M,S,T,U,V,a,b,c,i,ans=1e18;
    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;
    dij.push(make_pair(0,U));
    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));
        for(auto i:Next2[b]) dij.push(make_pair(a,i));

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

    for(i=1;i<=N;i++) small[i]=-1;
    dij.push(make_pair(0,V));
    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));
        for(auto i:Next2[b]) dij.push(make_pair(a,i));

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


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

    return 0;
}

Compilation message (stderr)

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

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