Submission #137467

#	Time	Username	Problem	Language	Result	Execution time	Memory
137467		MladenP	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	1661 ms	262148 KiB

commuter_pass

#include<bits/stdc++.h>
#define STIZE(x) fprintf(stderr, "STIZE%d\n", x);
#define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x);
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define mid (l+r)/2
#define endl '\n'
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 1000000000000000LL
#define INF 1000000000
#define EPS 1e-9
using namespace std;
#define MAXN 100010
int N, M, S, T, U, V;
lld dist1[MAXN], dist2[MAXN], dpU[MAXN], dpV[MAXN];
bool pos[MAXN];
vector<pair<int, lld> > adj[MAXN];
vector<int> topo, dag[MAXN];
pair<lld, lld> dp[MAXN];
priority_queue<pair<lld, int>, vector<pair<lld, int> >, greater<pair<lld, int > > > pq;
void topoSort(int node) {
    for(auto x : dag[node]) topoSort(x);
    topo.pb(node);
}
void dijkstra(lld dist[], int src) {
    for(int i = 1; i <= N; i++) dist[i] = pos[i] = 0;
    pq.push({0, src});
    while(!pq.empty()) {
        pii vrh = pq.top(); pq.pop();
        if(!pos[vrh.se]) {
            pos[vrh.se] = 1;
            dist[vrh.se] = vrh.fi;
            for(auto x : adj[vrh.se]) {
                if(!pos[x.fi]) pq.push({dist[vrh.se]+x.se, x.fi});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cerr.tie(0);
    cin >> N >> M >> S >> T >> U >> V;
    for(int i = 0; i < M; i++) {
        int A, B; lld C; cin >> A >> B >> C;
        adj[A].pb({B, C});
        adj[B].pb({A, C});
    }
    dijkstra(dist1, S);
    dijkstra(dist2, T);
    for(int i = 1; i <= N; i++) {
        for(auto j : adj[i]) {
            if(dist1[i]+j.se+dist2[j.fi] == dist1[T]) dag[i].pb(j.fi);
        }
    }
    topoSort(S);
    reverse(all(topo));
    dijkstra(dist1, U);
    dijkstra(dist2, V);
    while(!topo.empty()) {
        int node = topo.back(); topo.pop_back();
        dp[node] = {dist1[node], dist2[node]};
        dpU[node] = dist1[node];
        dpV[node] = dist2[node];
        for(auto x : dag[node]) {
            if(dpU[x] < dpU[node]) dpU[node] = dpU[x];
            if(dpV[x] < dpV[node]) dpV[node] = dpV[x];
            if(dp[x].fi+dp[x].se < dp[node].fi+dp[node].se) dp[node] = {dp[x].fi, dp[x].se};
        }
        if(dist1[node]+dpV[node] < dp[node].fi+dp[node].se) dp[node] = {dist1[node], dpV[node]};
        if(dist2[node]+dpU[node] < dp[node].fi+dp[node].se) dp[node] = {dpU[node], dist2[node]};
    }
    cout << min(dp[S].fi+dp[S].se, dist1[V]);
}

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