Submission #525932

#	Time	Username	Problem	Language	Result	Execution time	Memory
525932		Netr	Robot (JOI21_ho_t4)	C++14	0 / 100	82 ms	15504 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){
    priority_queue<pi, vector<pi>, greater<pi>> pq;
    fill(begin(D), end(D), INF);
    pq.push({D[src] = 0, src});
    while(!pq.empty()){
        int cdist, node;
        tie(cdist, node) = pq.top(); pq.pop();
        if(cdist != D[node]) continue;
        if(node == N) break;
        for(auto e : edges[node]){
            int cost = min(get<2>(e), cc[node][get<1>(e)] - get<2>(e));
            if(cdist + cost < D[get<0>(e)]){
                pq.push({D[get<0>(e)] = cdist + cost, get<0>(e)});
            }
        }
    }
}

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";
        exit(0);
    }
    djikstras(1);
    cout << D[N] << "\n";
}

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