Submission #439826

#	Time	Username	Problem	Language	Result	Execution time	Memory
439826		Deepesson	Robot (JOI21_ho_t4)	C++17	100 / 100	1002 ms	72408 KiB

Main

#include <bits/stdc++.h>
#define MAX 101000
typedef std::pair<long long,long long> pii;
typedef std::pair<long long,pii> pip;
std::vector<pip> con[MAX];
std::unordered_map<long long,long long> custao[MAX];
std::map<long long,long long> mamg[MAX];
int main()
{
    int N,M;
    std::cin>>N>>M;
    for(int i=0;i!=M;++i){
        long long a,b,c,d;
        std::cin>>a>>b>>c>>d;--a;--b;
        custao[a][c]+=d;
        custao[b][c]+=d;
        con[a].push_back({b,{c,d}});
        con[b].push_back({a,{c,d}});
    }
    std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
    queue.push({0,0});
    bool visitou[N]={};
    long long valores[N]={};
    long long custo=0;
    while(queue.size()){
        auto _ = queue.top();
        queue.pop();
        if(visitou[_.second])continue;
        visitou[_.second]=true;
        valores[_.second]=_.first;
        for(auto&x:con[_.second]){
            if(mamg[x.first].find(x.second.first)==mamg[x.first].end())
            mamg[x.first][x.second.first]=_.first;
            long long ajuda=_.first;
            auto it = mamg[_.second].find(x.second.first);
            if(it!=mamg[_.second].end())ajuda=it->second;
            queue.push({std::min(ajuda+custao[_.second][x.second.first]-x.second.second,_.first+x.second.second),x.first});
        }
    }
    if(!visitou[N-1]){
        printf("-1\n");return 0;
    }
    std::cout<<valores[N-1]<<"\n";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:24:15: warning: unused variable 'custo' [-Wunused-variable]
   24 |     long long custo=0;
      |               ^~~~~

• Subtask 1: 34 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42