제출 #1187420

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1187420		user736482	Robot (JOI21_ho_t4)	C++20	34 / 100	493 ms	109532 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL

ll a,b,c,d,t,n,m,l,q;
ll dst[100007];
bool odw[100007];
vector<pair<ll,pair<ll,ll>>>g[100007];
vector<pair<ll,ll>>g2[1000007];
map<ll,ll>mp[100007],sm[100007];
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    
    for(ll i=0;i<m;i++){
        cin>>a>>b>>c>>d;
        a--;
        b--;
        c--;
        g[a].pb({c,{b,d}});
        g[b].pb({c,{a,d}});
        sm[a][c]+=d;
        sm[b][c]+=d;
    }
    ll ak=0;
    for(ll i=0;i<n;i++){
        mp[i][-1]=ak++;
        for(auto it : sm[i]){
            mp[i][(it).ff]=ak++;
        }
    }
    for(ll i=0;i<n;i++){
        for(auto j : g[i]){
            g2[mp[i][-1]].pb({min(sm[i][j.ff]-j.ss.ss,j.ss.ss),mp[j.ss.ff][-1]});
            g2[mp[i][-1]].pb({0,mp[j.ss.ff][j.ff]});
            g2[mp[i][j.ff]].pb({sm[i][j.ff]-j.ss.ss,mp[j.ss.ff][-1]});
        }
    }
    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>pq;
    pq.push({0,0});
    for(ll i=0;i<ak;i++)dst[i]=INFL;
    while(pq.size()){
        auto pom=pq.top();
        pq.pop();
        if(odw[pom.ss])continue;
        odw[pom.ss]=1;
        dst[pom.ss]=pom.ff;
        for(pair<ll,ll> i : g2[pom.ss]){
            pq.push({i.ff+pom.ff,i.ss});
        }
    }
    if(dst[mp[n-1][-1]]==INFL)dst[mp[n-1][-1]]=-1;
    cout<<dst[mp[n-1][-1]];
    return 0;
}

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