Submission #1161375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161375		brinton	Robot (JOI21_ho_t4)	C++20	34 / 100	3095 ms	49748 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,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});
        total[a][color] += cost;
        total[b][color] += cost;
    }
    // vector<vector<int>> dist(N+1,vector<int>(M+2,inf));
    map<pair<int,int>,int> dist;

    priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> pq;
    // M+1 is king
    dist[{1,M+1}] = 0;
    dist[{1,M+1}] = 0;
    pq.push({0,1,M+1});// dist,idx,in_color
    while(!pq.empty()){
        auto [cdist,cur,ccolor] = pq.top();
        // cout << cur << " " << ccolor << " : " << cdist << " " << dist[cur][ccolor] << endl;
        pq.pop();
        if(dist[{cur,ccolor}] != cdist)continue;
        // cout << cur << " " << ccolor << " : " << cdist << endl;
        if(ccolor == M+1){
            // this is a king node
            // cout << "A" << endl;
            for(auto [nxt,color,w]:edges[cur]){
                // cout << nxt << " " << endl;
                // to color node, chose direct
                if(!dist.count({nxt,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.count({nxt,M+1}) || ndist < dist[{nxt,M+1}]){
                    dist[{nxt,M+1}] = ndist;
                    pq.push({ndist,nxt,M+1});
                }
            }
        }else{
            // cout << "A" << endl;
            for(auto [nxt,color,w]:edges[cur]){
                // choose other, so become king node
                if(color == ccolor && (!dist.count({nxt,M+1}) || total[cur][color]-w+cdist < dist[{nxt,M+1}])){
                    dist[{nxt,M+1}] = total[cur][color]-w+cdist;
                    pq.push({dist[{nxt,M+1}],nxt,M+1});
                }
            }
        }
    }
    if(!dist.count({N,M+1})){
        cout << "-1";
    }else{
        cout << dist[{N,M+1}];
    }
}

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