Submission #137464

#	Time	Username	Problem	Language	Result	Execution time	Memory
137464		MladenP	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	1691 ms	262144 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];
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] = {INF, INF};
        for(auto x : dag[node]) {
            if(dp[x].fi+dp[x].se < dp[node].fi+dp[node].se) dp[node] = dp[x];
        }
        dp[node].fi = min(dp[node].fi, dist1[node]);
        dp[node].se = min(dp[node].se, 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