Submission #331777

#	Time	Username	Problem	Language	Result	Execution time	Memory
331777		daniel920712	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	2077 ms	262148 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;
queue < int > ttt;
bool use[200005]={0};
bool have[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));

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

    }

    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:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
commuter_pass.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |     scanf("%d %d %d %d",&S,&T,&U,&V);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |         scanf("%d %d %d",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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