Submission #331776

#	Time	Username	Problem	Language	Result	Execution time	Memory
331776		daniel920712	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	390 ms	38368 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 < int , pair < int , int > > > Next[1000005];
priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > dij;
bool use[200005]={0};
int small[100005]={0};
int main()
{
    int N,M,S,T,U,V,a,b,c,i;
    scanf("%d %d",&N,&M);
    scanf("%d %d %d %d",&S,&T,&U,&V);
    for(i=1;i<=N;i++) small[i]=-1;
    for(i=0;i<M;i++)
    {
        scanf("%d %d %d",&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));

    }
    for(i=1;i<=N;i++)
    {
        for(auto j:Next[i])
        {
            if(small[i]+j.second.second==small[j.second.first]) use[j.first]=1;
        }
    }
    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*(1-use[i.first]),i.second.first));

    }
    printf("%d\n",small[V]);

    return 0;
}

Compilation message (stderr)

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

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