제출 #531962

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
531962		Netr	Robot (JOI21_ho_t4)	C++14	0 / 100	96 ms	25820 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 int INF = 1ll<<60;
 
int N,M,V[MAXN], D[MAXN];
map<int, vector<pi>> edges[MAXN];
map<int, int> cc[MAXN], 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";
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp:15:20: warning: overflow in conversion from 'long long int' to 'int' changes value from '1152921504606846976' to '0' [-Woverflow]
   15 | const int INF = 1ll<<60;
      |                 ~~~^~~~

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