Submission #833573

#	Time	Username	Problem	Language	Result	Execution time	Memory
833573		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	24 / 100	91 ms	13164 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long

int n, m;
int s, t;
int u, v;
vector<vector<pair<int,int>>> edg;
bool vis[100005];
ll distS[100005];
ll distT[100005];
ll distU[100005];
ll distV[100005];
ll dist[305][305];

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

    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;
    edg.resize(n+5);
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            dist[i][j] = 1e18;
            if (i == j) dist[i][j] = 0;
        }
    }
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edg[a].push_back({b,c});
        edg[b].push_back({a,c});
        dist[a][b] = c;
        dist[b][a] = c;
    }

    priority_queue<pair<ll,int>> q;
    q.push({0,s});
    for (int i = 0; i <= n; i++) distS[i] = 1e18, vis[i] = 0;
    distS[s] = 0;
    while (!q.empty()) {
        int f = q.top().second;
        q.pop();
        if (vis[f]) continue;
        vis[f] = 1;
        for (auto &[i,j] : edg[f]) {
            if (!vis[i] && distS[i] > (ll) distS[f] + j) {
                distS[i] = (ll) distS[f] + j;
                q.push({-distS[i], i});
            }
        }
    }

    q.push({0,t});
    for (int i = 0; i <= n; i++) distT[i] = 1e18, vis[i] = 0;
    distT[t] = 0;
    while (!q.empty()) {
        int f = q.top().second;
        q.pop();
        if (vis[f]) continue;
        vis[f] = 1;
        for (auto &[i,j] : edg[f]) {
            if (!vis[i] && distT[i] > (ll) distT[f] + j) {
                distT[i] = (ll) distT[f] + j;
                q.push({-distT[i], i});
            }
        }
    }

    q.push({0,u});
    for (int i = 0; i <= n; i++) distU[i] = 1e18, vis[i] = 0;
    distU[u] = 0;
    while (!q.empty()) {
        int f = q.top().second;
        q.pop();
        if (vis[f]) continue;
        vis[f] = 1;
        for (auto &[i,j] : edg[f]) {
            if (!vis[i] && distU[i] > (ll) distU[f] + j) {
                distU[i] = (ll) distU[f] + j;
                q.push({-distU[i], i});
            }
        }
    }

    q.push({0,v});
    for (int i = 0; i <= n; i++) distV[i] = 1e18, vis[i] = 0;
    distV[v] = 0;
    while (!q.empty()) {
        int f = q.top().second;
        q.pop();
        if (vis[f]) continue;
        vis[f] = 1;
        for (auto &[i,j] : edg[f]) {
            if (!vis[i] && distV[i] > (ll) distV[f] + j) {
                distV[i] = (ll) distV[f] + j;
                q.push({-distV[i], i});
            }
        }
    }

    ll ans = distU[v], Le = 1e18, Ri = 1e18;
    for (int i = 1; i <= n; i++) {
        if (distS[t] == distS[i] + distT[i]) {
            Le = min(Le, distV[i]);
            Ri = min(Ri, distU[i]);
        }
    }
    ans = min(ans, Le + Ri);
    //cout << ans << '\n';

    //cerr << "S: "; for (int i = 1; i <= n; i++) { cerr << distS[i] << " \n" [i == n]; }
    //cerr << "T: "; for (int i = 1; i <= n; i++) { cerr << distT[i] << " \n" [i == n]; }
    //cerr << "V: "; for (int i = 1; i <= n; i++) { cerr << distV[i] << " \n" [i == n]; }
    
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    ans = distU[v];
    for (int i = 1; i <= n; i++) {
        if (distS[i] + distT[i] != distS[t]) continue;
        for (int j = 1; j <= n; j++) {
            if (distS[j] + distT[j] != distS[t]) continue;
            if (distS[i] + dist[i][j] + distT[j] == distS[t]
              || distS[j] + dist[j][i] + distT[i] == distS[t]
               ) { 
                ans = min(ans, distU[i] + distV[j]);
                ans = min(ans, distV[i] + distU[j]);
            }
        }
    }
    cout << ans << '\n';

    return 0;
}

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