Submission #1222529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222529		mingga	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	346 ms	63624 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 * 4];
int n, m, A, B, C, D;
int f[4][N * 4];

void dijkstra(int st, int id) {
    // for(int i = 1; i <= n; i++) f[id][i] = inf;
    memset(f[id], 0x3f, sizeof f[id]);
    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});
            }
        }
    }
}

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[u + 3 * n].pb({v + 3 * n, w});
        g[v].pb({u, w});
        g[v + 3 * n].pb({u + 3 * n, w});
    }
    dijkstra(A, 0);
    dijkstra(B, 1);
    for(int i = 1; i <= n; i++) {
    	g[i].pb({i + n, 0});
    	g[i].pb({i + n * 2, 0});
    	g[i + n].pb({i + n * 3, 0});
    	g[i + n * 2].pb({i + n * 3, 0});
    }
    for(int u = 1; u <= n; u++) {
    	for(auto x : g[u]) {
    		int v = x.fi, w = x.se;
    		if(f[0][u] + w + f[1][v] == f[0][B]) {
    			g[u + n].pb({v + n, 0});
    			g[v + n * 2].pb({u + n * 2, 0});
    		}
    	}
    }
    dijkstra(C, 2);
    cout << f[2][D + n * 3] << ln;
}

Compilation message (stderr)

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

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