Submission #137472

#	Time	Username	Problem	Language	Result	Execution time	Memory
137472		MladenP	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	583 ms	29924 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], dp[MAXN], dpU[MAXN], dpV[MAXN];
bool pos[MAXN];
vector<pair<int, lld> > adj[MAXN];
vector<int> topo, dag[MAXN];
priority_queue<pair<lld, int>, vector<pair<lld, int> >, greater<pair<lld, int > > > pq;
void topoSort(int node) {
    pos[node] = true;
    for(auto x : dag[node]) if(!pos[x]) 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()) {
        pair<lld,int> 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);
        }
    }
    for(int i = 1; i <= N; i++) pos[i] = 0;
    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]) {
            dpU[node] = min(dpU[node], dpU[x]);
            dpV[node] = min(dpV[node], dpV[x]);
            dp[node] =  min(dp[node],  dp[x]);
        }
        dp[node] = min(dp[node], dist1[node]+dpV[node]);
        dp[node] = min(dp[node], dpU[node]+dist2[node]);
    }
    cout << min(dp[S], dist1[V]) << endl;
}

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