제출 #1181442

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181442		pythontest	Robot (JOI21_ho_t4)	C++20	58 / 100	3099 ms	81528 KiB

Main

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
using namespace std;
constexpr int N=2e5+30;
struct krawedz{
    int to;
    long long koszt;
    int tc;
    int sc;
    int color;
    bool operator<(const krawedz& a) const{
        return this->color<a.color;
    }
};
vector<krawedz> graf[N];
vector<long long> sumawpunkcie[N],odleglosc[N];
vector<int> krawedzieprzef[N];
unordered_map<int,int> mapowania[N];
int main() {
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++){
        int a,b,c,p;
        scanf("%d %d %d %d",&a,&b,&c,&p);
        graf[a].push_back({b,p,-1,-1,c});
        graf[b].push_back({a,p,-1,-1,c});
    }
    for(int i=1;i<=n;i++){
        int licznik=1;
        sort(graf[i].begin(),graf[i].end());
        sumawpunkcie[i].push_back(0);
        odleglosc[i].push_back(1e17);
        krawedzieprzef[i].push_back(-1);
        for(int j=0;j<graf[i].size();j++){
            auto &x = graf[i][j];
            if(!mapowania[i].contains(x.color)) {
                x.sc=licznik;
                mapowania[i][x.color]=licznik++;
                sumawpunkcie[i].push_back(x.koszt);
                odleglosc[i].push_back(1e17);
                krawedzieprzef[i].push_back(j);
            }
            else {
                x.sc=mapowania[i][x.color];
                sumawpunkcie[i][mapowania[i][x.color]]+=x.koszt;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(auto &x:graf[i]){
            x.tc=mapowania[x.to][x.color];
        }
    }
    priority_queue<pair<long long, pair<int,int>>> kolejka;
    odleglosc[1][0]=0;
    kolejka.push({0,{1,0}});
    while(!kolejka.empty()){
        auto top = kolejka.top();
        kolejka.pop();
        top.first=-top.first;
        if(top.second.second==0){
            for(auto &x:graf[top.second.first]){
                if(odleglosc[x.to][0]>odleglosc[top.second.first][0]+min(x.koszt,sumawpunkcie[top.second.first][x.sc]-x.koszt)){
                    odleglosc[x.to][0]=odleglosc[top.second.first][0]+min(x.koszt,sumawpunkcie[top.second.first][x.sc]-x.koszt);
                    kolejka.push({-odleglosc[x.to][0],{x.to,0}});
                }
                if(odleglosc[x.to][x.tc]>top.first){
                    odleglosc[x.to][x.tc]=top.first;
                    kolejka.push({-odleglosc[x.to][x.tc],{x.to,x.tc}});
                }
            }
        }
        else{
            for(int j=krawedzieprzef[top.second.first][top.second.second];j<graf[top.second.first].size();j++){
                auto x = graf[top.second.first][j];
                if(x.sc!=top.second.second)
                    break;
                if(odleglosc[x.to][0]>top.first+sumawpunkcie[top.second.first][x.sc]-x.koszt){
                    odleglosc[x.to][0]=top.first+sumawpunkcie[top.second.first][x.sc]-x.koszt;
                    kolejka.push({-odleglosc[x.to][0],{x.to,0}});
                }
            }
        }
    }
    if(odleglosc[n][0]==1e17) printf("-1\n");
    else printf("%lld",odleglosc[n][0]);
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%d %d %d %d",&a,&b,&c,&p);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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