제출 #1157443

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157443		andrewp	Commuter Pass (JOI18_commuter_pass)	C++20	16 / 100	163 ms	27108 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int ll
const int N=1e5+10;
const ll inf=(ll)(1e18);

int n, m, s, t, u, v, dist[N][3];
vector<pii> g[N];
vector<int> adj[N];
int ans=inf;
bool was[N];
pii dp[N];

void Dijkstra(int root, int tp) {
    vector<bool> vis(n+1, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, root));
    for (int i=1; i<=n; i++)
        dist[i][tp]=inf;
    dist[root][tp]=0;
    while (pq.size()) {
        int x=pq.top().second;
        pq.pop();
        if (vis[x])
            continue;
        vis[u]=true;
        for (auto z:g[x]) {
            int p, q;
            tie(p, q)=z;
            if (dist[p][tp]>dist[x][tp]+q) {
                dist[p][tp]=dist[x][tp]+q;
                pq.push(make_pair(dist[p][tp], p));
            }
        }
    }
}

void dfs(int x) {
    if (was[x])
        return;
    was[x]=true;
    dp[x]={inf, inf};
    if (x==t)
        dp[x]={dist[x][1], dist[x][2]};
    for (auto u:adj[x]) {
        dfs(u);
        dp[x].first=min(dp[x].first, dp[u].first);
        dp[x].second=min(dp[x].second, dp[u].second);
    }
    if (dp[x].first!=inf) {
        dp[x].first=min(dp[x].first, dist[x][1]);
        dp[x].second=min(dp[x].second, dist[x][2]);
        ans=min(ans, min(dist[x][1]+dp[x].second, dist[x][2]+dp[x].first));
    }
}

int32_t main () {
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n >> m >> s >> t >> u >> v;
    for (int i=1; i<=m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].pb(make_pair(b, w));
        g[b].pb(make_pair(a, w));
    }
    Dijkstra(s, 0);
    Dijkstra(u, 1);
    Dijkstra(v, 2);
    for (int i=1; i<=n; i++) {
        for (auto u:g[i]) {
            if (dist[i][0]+u.second==dist[u.first][0]) {
                adj[i].pb(u.first);
            }
        }
    }
    dfs(s);
    cout << min(ans, dist[v][1]) << '\n';
    return 0;
}

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