제출 #1162850

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162850		brinton	Robot (JOI21_ho_t4)	C++20	100 / 100	708 ms	100392 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf (long long)(1e15)
signed main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    //start here
    int N,M;
    cin >> N >> M;
    vector<vector<array<int,3>>> edges(N+1);
    vector<map<int,vector<pair<int,int>>>> color_edges(N+1);
    vector<map<int,int>> total(N+1);
    for(int i = 0;i < M;i++){
        int a,b,color,cost;
        cin >> a >> b >> color >> cost;
        edges[a].push_back({b,color,cost});
        edges[b].push_back({a,color,cost});
        color_edges[a][color].push_back({b,cost});
        color_edges[b][color].push_back({a,cost});
        total[a][color] += cost;
        total[b][color] += cost;
    }
    vector<map<int,int>> dist(N+1);
    priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> pq;
    // M+1 is king
    dist[1][M+1] = 0;
    pq.push({0,1,M+1});// dist,idx,in_color
    while(!pq.empty()){
        auto [cdist,cur,ccolor] = pq.top();
        pq.pop();
        if(dist[cur][ccolor] != cdist)continue;
        if(ccolor == M+1){
            // this is a king node
            for(auto [nxt,color,w]:edges[cur]){
                // to color node, chose direct
                if(!dist[nxt].count(color) || cdist+w-w < dist[nxt][color]){
                    dist[nxt][color] = cdist+w-w;
                    pq.push({dist[nxt][color],nxt,color});
                }
                // to king node, chose direct or indirect
                int ndist = cdist+min(w,total[cur][color]-w);
                if(!dist[nxt].count(M+1) || ndist < dist[nxt][M+1]){
                    dist[nxt][M+1] = ndist;
                    pq.push({ndist,nxt,M+1});
                }
            }
        }else{
            for(auto [nxt,w]:color_edges[cur][ccolor]){
                // choose other, so become king node
                if((!dist[nxt].count(M+1) || total[cur][ccolor]-w+cdist < dist[nxt][M+1])){
                    dist[nxt][M+1] = total[cur][ccolor]-w+cdist;
                    pq.push({dist[nxt][M+1],nxt,M+1});
                }
            }
        }
    }
    if(!dist[N].count(M+1)){
        cout << "-1";
    }else{
        cout << dist[N][M+1];
    }
}

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