Submission #531967

#	Time	Username	Problem	Language	Result	Execution time	Memory
531967		Netr	Robot (JOI21_ho_t4)	C++14	100 / 100	853 ms	85428 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
typedef tuple<ll,ll,ll> ti;
 
#ifdef DEBUG
#define D(x...) printf(x);
#else
#define D(x...)
#endif
 
const ll MAXN = 1e5 + 5;
const ll MAXM = 2e5 + 5;
const ll INF = 1ll<<60;
 
ll N,M,V[MAXN],D[MAXN];
map<ll, vector<pi>> edges[MAXN];
map<ll, ll> cc[MAXN], dp[MAXN];

void djikstras(ll src){
    fill(begin(D), end(D), INF);
    priority_queue<ti, vector<ti>, greater<ti>> pq;
    pq.push({D[src] = 0, src, 0});

    while(!pq.empty()){
        ll cdist, node, col;
        tie(cdist, node, col) = pq.top(); pq.pop();


        // if we're entering this node on an edge that was recoloured WITH the intention to leave this node on an edge with the ORIGINAL colour of the recoloured edge
        // we do this to avoid double counting the cost of recolouring the first edge
        if(col){
            if(dp[node][col] != cdist) continue;
            for(auto e : edges[node][col]){

                // outgoing edge uses the ORIGINAL colour and we include the cost of recolouring the previous edge
                ll cost = cc[node][col] - e.second + cdist;
                if(D[e.first] > cost){
                    pq.push({D[e.first] = cost, e.first, 0});
                }
            }
        }else{
            // standard entry to a node, available options are:
            // 1) recolour all same-coloured edges
            // 2) recolour edge to the "free" colour (existence proven by PHP), no intention to use the original colour in the next node (we don't need to do anything special, if it's double counted that's ok - best solution will come from option 3)
            // 3) recolour edge to the "free" colour, intending to use the original colour in the next node
            
            if(D[node] != cdist) continue;
            for(auto &c : edges[node]){
                for(auto e : c.second){

                    // Option 1
                    ll c1 = cc[node][c.first] - e.second + cdist;
                    if(D[e.first] > c1){
                        pq.push({D[e.first] = c1, e.first, 0});
                    }

                    // Option 2 (include price of recolouring)
                    ll c2 = e.second + cdist;
                    if(D[e.first] > c2){
                        pq.push({D[e.first] = c2, e.first, 0});
                    }

                    // Option 3 (don't include price of recolouring)
                    ll c3 = cdist;
                    if(!dp[e.first].count(c.first) || dp[e.first][c.first] > c3){
                        pq.push({dp[e.first][c.first] = c3, e.first, c.first});
                    }
                }
            }
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> M;
    for(int i = 0; i < M; i++){
        ll ai, bi, ci, pi;
        cin >> ai >> bi >> ci >> pi;
        edges[ai][ci].push_back({bi, pi});
        edges[bi][ci].push_back({ai, pi});
        cc[ai][ci] += pi;
        cc[bi][ci] += pi;
    }
    djikstras(1);
    cout << (D[N] == INF ? -1 : D[N]) << "\n";
}

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