Submission #1015571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015571		fryingduc	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	211 ms	35968 KiB

commuter_pass

#include "bits/stdc++.h"
using namespace std;

#define int long long

const int maxn = 1e5 + 5;
const int inf = 1e18;
int n, m;
vector<pair<int, int>> g[maxn];
vector<int> rev_adj[maxn];
vector<int> adj[maxn];
int A, B, C, D;
int da[maxn], db[maxn], dc[maxn], dd[maxn];
int ans = inf;

int vis[maxn];
int f[maxn], rev_f[maxn];
vector<int> topo;
vector<int> rev_topo;

void dijkstra(int &s, int d[]) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for(int i = 1; i <= n; ++i) {
        d[i] = inf;
    }
    pq.push({0, s});
    d[s] = 0;
    while(!pq.empty()) {
        int u = pq.top().second, dist = pq.top().first;
        pq.pop();
        for(auto e:g[u]) {
            int v = e.first, w = e.second;
            if(d[v] > dist + w) {
                d[v] = dist + w;
                pq.push({d[v], v});
            }
        }
    }
}
void dfs(int u) {
    vis[u] = 1;
    f[u] = dc[u], rev_f[u] = dd[u];
    for(auto v:adj[u]) {
        if(!vis[v]) {
            dfs(v);
        }
        f[u] = min(f[u], f[v]);
        rev_f[u] = min(rev_f[u], rev_f[v]);
    }
    rev_topo.push_back(u);
    vis[u] = 2;
}
void solve() {
    cin >> n >> m >> A >> B >> C >> D;
    for(int i = 1; i <= m; ++i) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    dijkstra(A, da);
    dijkstra(B, db);
    dijkstra(C, dc);
    dijkstra(D, dd);
    
    for(int u = 1; u <= n; ++u) {
        for(auto e:g[u]) {
            int v = e.first, w = e.second;
            
            if(da[u] + db[v] + w == da[B]) { 
                adj[u].push_back(v);
                rev_adj[v].push_back(u);
            }
        }
    }
    for(int i = 1; i <= n; ++i) {
        if(!vis[i]) dfs(i);
    }
    int ans = inf;
    for(int u = 1; u <= n; ++u) {
        ans = min({ans, dc[u] + rev_f[u], dd[u] + f[u]});
    }
    cout << ans;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

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