Submission #1222524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222524		mingga	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	218 ms	29724 KiB

commuter_pass

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

#define int long long
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) (x).size()
#define ln '\n'
const int N = 1e5 + 7;
const int inf = 2e18;
vector<pair<int, int>> g[N];
int n, m, A, B, C, D;
int f[4][N];

void dijkstra(int st, int id) {
    for(int i = 1; i <= n; i++) f[id][i] = inf;
    priority_queue<pair<int, int>> q;
    f[id][st] = 0;
    q.push({0, st});
    while(sz(q)) {
        auto cur = q.top(); q.pop();
        int u = cur.se, W = -cur.fi;
        if(W > f[id][u]) continue;
        for(auto y : g[u]) {
            int v = y.fi, w = y.se;
            if(f[id][v] > W + w) {
                f[id][v] = W + w;
                q.push({-f[id][v], v});
            }
        }
    }
}

vector<pair<int, int>> dag[N];
int indeg[N];

int calc(int i1, int i2, int st, int en) {
    for(int i = 1; i <= n; i++) dag[i].clear();
    int path = f[i1][en];
//    cout << "TURN " << st << ' ' << en << ' ' << path << ln;
    for(int u = 1; u <= n; u++) {
        for(auto x : g[u]) {
            int v = x.fi, w = x.se;
            if(f[i1][u] + w + f[i2][v] == path or f[i1][v] + w + f[i2][u] == path) {
//                cerr << u << ' ' << v << ' ' << f[i1][u] << ' ' << f[i1][v] << ln;
                if(f[i1][u] < f[i1][v]) dag[u].pb({v, 0});
                else dag[u].pb({v, w});
            } else {
                dag[u].pb({v, w});
            }
        }
    }
//    for(int i = 1; i <= n; i++) {
//        for(auto x : dag[i]) {
//            cerr << i << ' ' << x.fi << ' ' << x.se << ln;
//        }
//    }
    priority_queue<pair<int, int>> q;
    for(int i = 1; i <= n; i++) f[2][i] = inf;
    f[2][C] = 0;
    q.push({0, C});
    while(sz(q)) {
        auto cur = q.top(); q.pop();
        int u = cur.se, W = -cur.fi;
        if(W > f[2][u]) continue;
//        cerr <<"PAR: " << u << ' ' << W << ln;
        for(auto y : dag[u]) {
            int v = y.fi, w = y.se;
//            cerr << v << ' ' << w << ln;
            if(f[2][v] > W + w) {
                f[2][v] = W + w;
                q.push({-f[2][v], v});
            }
        }
    }
    return f[2][D];
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    if(fopen("tunnel.inp", "r")) {
        freopen("tunnel.inp", "r", stdin);
        freopen("tunnel.out", "w", stdout);
    }
    cin >> n >> m;
    cin >> A >> B >> C >> D;
    for(int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    dijkstra(A, 0);
    dijkstra(B, 1);
//    cout << calc(0, 1, A, B);
    cout << min(calc(0, 1, A, B), calc(1, 0, B, A));
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen("tunnel.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         freopen("tunnel.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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