Submission #531964

#	Time	Username	Problem	Language	Result	Execution time	Memory
531964		Netr	Robot (JOI21_ho_t4)	C++14	0 / 100	852 ms	71440 KiB

Main

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

void djikstras(int 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;
        int 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
                int cost = cc[node][col] - e.second + cdist;
                if(D[e.first] > cdist + 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
                    int 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)
                    int 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)
                    int 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++){
        int 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: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42