Submission #1181433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181433		pythontest	Robot (JOI21_ho_t4)	C++20	24 / 100	313 ms	104216 KiB

Main

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;
constexpr int N=2e5+30;
struct krawedz{
    int to;
    long long koszt;
    int tc;
    int sc;
    int color;
};
vector<krawedz> graf[N];
vector<long long> sumawpunkcie[N],odleglosc[N];
vector<vector<krawedz>> 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;
        sumawpunkcie[i].push_back(0);
        odleglosc[i].push_back(1e17);
        krawedzieprzef[i].push_back({});
        for(auto &x:graf[i]){
            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({x});
            }
            else {
                x.sc=mapowania[i][x.color];
                sumawpunkcie[i][mapowania[i][x.color]]+=x.koszt;
                krawedzieprzef[i][mapowania[i][x.color]].push_back(x);
            }
        }
    }
    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-x.koszt){
                    odleglosc[x.to][x.tc]=top.first-x.koszt;
                    kolejka.push({-odleglosc[x.to][x.tc],{x.to,x.tc}});
                }
            }
        }
        else{
            for(auto x: krawedzieprzef[top.second.first][top.second.second]){
                if(odleglosc[x.to][0]>top.first+sumawpunkcie[top.second.first][x.sc]){
                    odleglosc[x.to][0]=top.first+sumawpunkcie[top.second.first][x.sc];
                    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;
}

Compilation message (stderr)

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

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