Submission #1253237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253237		dex111222333444555	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	2093 ms	18532 KiB

commuter_pass

#include <bits/stdc++.h>
#define ii pair<int, int>
#define lli pair<long long, int>
#define fi first
#define se second
#define all(v) begin(v), end(v)
#define dbg(x) "[" #x " = " << x << "]"
using namespace std;
const int MAXN = 1e5 + 5;

template<class X, class Y>
    bool minimize(X &x, const Y &y){
        if (x > y){
            x = y; return 1;
        }
        return 0;
    }

template<class X, class Y>
    bool maximize(X &x, const Y &y){
        if (x < y){
            x = y; return 1;
        }
        return 0;
    }

struct edge{
    int u, v, w;
    edge(int _u = 0, int _v = 0, int _w = 0):
        u(_u), v(_v), w(_w) {};
    int other(int x){
        return u ^ v ^ x;
    }
};

int numNode, numEdge, staX, finX, staY, finY, par[MAXN];
long long dist[MAXN];
vector<int> adj[MAXN], nadj[MAXN];
edge e[MAXN << 1];

void dijsktra(int sta, int fin){
    priority_queue<lli, vector<lli>, greater<lli>> q;
    memset(dist, 0x3f, sizeof dist);
    q.push(lli(dist[sta] = 0, sta));
    int cnt = 0;
    while(q.size()){
        int u = q.top().se;
        long long len = q.top().fi;
        q.pop();
        if (len > dist[u]) continue;
        for(int id: adj[u]){
            int v = e[id].other(u);
            if (minimize(dist[v], dist[u] + e[id].w)) q.push(lli(dist[v], v));
        }
    }
}

void bfs(int sta, int fin){
    queue<int> q;
    memset(dist, -0x3f, sizeof dist);
    q.push(sta); dist[sta] = 0;
    while(q.size()){
        int u = q.front(); q.pop();
        for(int id: nadj[u]){
            int v = e[id].other(u);
            if (maximize(dist[v], dist[u] + 1)) q.push(v), par[v] = id;
        }
    }
    while(fin != sta){
        e[par[fin]].w = 0;
        fin = e[par[fin]].other(fin);
    }
}

void input(){
    cin >> numNode >> numEdge >> staX  >> finX >> staY >> finY;
    for(int i = 1; i <= numEdge; i++){
        cin >> e[i].u >> e[i].v >> e[i].w;
        adj[e[i].u].push_back(i);
        adj[e[i].v].push_back(i);
    }
}

void solve(){
    dijsktra(staX, finX);
    for(int id = 1; id <= numEdge; id++){
        if (dist[e[id].u] == dist[e[id].v] + e[id].w){
            nadj[e[id].v].push_back(id);
        }else if (dist[e[id].v] == dist[e[id].u] + e[id].w){
            nadj[e[id].u].push_back(id);
        }
    }
    bfs(staX, finX);
    dijsktra(staY, finY);
    cout << dist[finY] << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solve();
}

• Subtask 1: 0 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45