제출 #1145148

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1145148		SnowRaven52	Robot (JOI21_ho_t4)	C++20	100 / 100	618 ms	67376 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define MAX 101000
typedef pair<long long,long long> pii;
typedef pair<long long,pii> pip;
vector<pip> con[MAX];
unordered_map<long long,long long> custao[MAX];
map<long long,long long> mamg[MAX];
int main(){
	// freopen("main.in", "r", stdin);
	// freopen(".out", "w", stdout);
    int n,m;
    cin>>n>>m;
    for(int i=0;i!=m;++i){
        long long a,b,c,d;
        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}});
    }
    priority_queue<pii,vector<pii>,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({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;
    }
    cout<<valores[n-1]<<"\n";
}

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