Submission #1156887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156887		irmuun	Robot (JOI21_ho_t4)	C++20	100 / 100	682 ms	83144 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const ll N=1e5+5;

map<ll,vector<array<ll,3>>>g[N];
ll dp[N];
map<ll,ll>dp2[N],psum[N];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,m;
    cin>>n>>m;
    for(ll i=1;i<=m;i++){
        ll a,b,c,p;
        cin>>a>>b>>c>>p;
        g[a][c].pb({b,c,p});
        g[b][c].pb({a,c,p});
        psum[a][c]+=p;
        psum[b][c]+=p;
    }
    priority_queue<array<ll,3>,vector<array<ll,3>>,greater<array<ll,3>>>pq;
    const ll inf=(ll)1e18;
    fill(dp,dp+N,inf);
    pq.push({0,1,0});
    dp[1]=0;
    while(!pq.empty()){
        auto [cost,x,c]=pq.top();
        pq.pop();
        if(c!=0){
            if(dp2[x][c]!=cost) continue;
            for(auto [y,col,p]:g[x][c]){
                ll case1=psum[x][col]-p;
                if(cost+case1<dp[y]){
                    dp[y]=cost+case1;
                    pq.push({dp[y],y,0});
                }
            }
        }
        else{
            if(dp[x]!=cost) continue;
            for(auto edges:g[x]){
                for(auto [y,col,p]:edges.second){
                    ll case1=psum[x][col]-p;
                    if(cost+case1<dp[y]){
                        dp[y]=cost+case1;
                        pq.push({dp[y],y,0});
                    }
                    ll case2=p;
                    if(cost+case2<dp[y]){
                        dp[y]=cost+case2;
                        pq.push({dp[y],y,0});
                    }
                    ll case3=cost;
                    if(!dp2[y].count(col)||case3<dp2[y][col]){
                        dp2[y][col]=case3;
                        pq.push({dp2[y][col],y,col});
                    }
                }
            }
        }
    }
    cout<<(dp[n]<inf?dp[n]:-1);
}

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