제출 #331778

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
331778		daniel920712	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	2086 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 < long long , pair < long long , long long > > > Next[1000005];
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;
    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;
        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("%lld\n",small[V]);

    return 0;
}

컴파일 시 표준 에러 (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("%lld %lld",&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("%lld %lld %lld %lld",&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("%lld %lld %lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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