Submission #525963

#	Time	Username	Problem	Language	Result	Execution time	Memory
525963		Netr	Robot (JOI21_ho_t4)	C++14	0 / 100	79 ms	16312 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int,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 = 1<<30;

int N,M,V[MAXN], D[MAXN];
vector<ti> edges[MAXN];
map<int, int> cc[MAXN];

bool dfs(int curr, int dest){
    V[curr] = 1;
    if(curr == dest) return true;
    bool res = false;
    for(auto e : edges[curr]){
        if(!V[get<0>(e)]) res |= dfs(get<0>(e), dest);
    }
    return res;
}

void djikstras(int src){
    using tip = tuple<int, int, pair<int, int>>;
    priority_queue<tip, vector<tip>, greater<tip>> pq;
    fill(begin(D), end(D), INF);
    fill(begin(V), end(V), 0);
    pq.push({D[src] = 0, src, {0,0}});
    while(!pq.empty()){
        int cdist, node;
        pi update;
        tie(cdist, node, update) = pq.top(); pq.pop();
        if(cdist != D[node] && update == make_pair(0,0)) continue;
        D("%d (%d)\n", node, cdist);
        if(node == N) break;
        V[node] = 1;
        cc[node][update.first] -= update.second;
        for(auto e : edges[node]){
            if(V[get<0>(e)]) continue;
            D("Node: %d, Colour: %d, cost: %d\n", node, get<1>(e), cc[node][get<1>(e)]);
            int cost = min(get<2>(e), cc[node][get<1>(e)] - get<2>(e));
            if(cdist + cost < D[get<0>(e)]){
                D("pushing: {%d, %d}\n", cdist+cost, get<0>(e));
                pi nu = (get<2>(e) < cc[node][get<1>(e)] - get<2>(e)) ? make_pair(get<1>(e), get<2>(e)) : make_pair(0,0);
                pq.push({D[get<0>(e)] = cdist + cost, get<0>(e), nu});
            }
        }
    }
}

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].push_back({bi, ci, pi});
        edges[bi].push_back({ai, ci, pi});
        if(cc[ai].find(ci) != cc[ai].end()){
            cc[ai][ci] += pi;
            cc[bi][ci] += pi;
        }else{
            cc[ai][ci] = pi;
            cc[bi][ci] = pi;
        }
    }
    if(!dfs(1, N)){
        cout << -1 << "\n";
    }else{
        djikstras(1);
        cout << D[N] << "\n";
    }
}

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