Submission #1155437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155437		CrabCNH	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	503 ms	69364 KiB

commuter_pass

#include <bits/stdc++.h>

#define task   "BriantheCrab"

#define int    long long
#define pii    pair <int, int>
#define fi     first
#define se     second
#define szf    sizeof
#define sz(s)  (int)((s).size())

using namespace std;

template <class T> void mini (T &t, T f) {if (t > f) t = f;}
template <class T> void maxi (T &t, T f) {if (t < f) t = f;}

const int maxN = 1e5 + 5;
const int inf = 1e18 + 7;
const int mod = 1e9 + 7;

struct Edge {
    int node, dis;
};

struct cmp {
    bool operator () (Edge A, Edge B) {
        return A.dis > B.dis; 
    }
};

int n, m, S, T, U, V;
int Ls[maxN], Lt[maxN], L[maxN * 4];
vector <Edge> adj[maxN], g[maxN * 4];

void dijkstraST () {
    priority_queue <Edge, vector <Edge>, cmp> pq;
    for (int i = 1; i <= n; i ++) {
        Ls[i] = Lt[i] = inf;
    }
    Ls[S] = 0;
    pq.push ({S, Ls[S]});
    while (!pq.empty ()) {
        auto [u, c] = pq.top ();
        pq.pop ();
        if (c > Ls[u]) {
            continue;
        }
        for (auto [v, w] : adj[u]) {
            if (Ls[v] > Ls[u] + w) {
                Ls[v] = Ls[u] + w;
                pq.push ({v, Ls[v]});
            }
        }
    }
    Lt[T] = 0;
    pq.push ({T, Lt[T]});
    while (!pq.empty ()) {
        auto [u, c] = pq.top ();
        pq.pop ();
        if (c > Lt[u]) {
            continue;
        }
        for (auto [v, w] : adj[u]) {
            if (Lt[v] > Lt[u] + w) {
                Lt[v] = Lt[u] + w;
                pq.push ({v, Lt[v]});
            }
        }
    }
}

void dijkstraUV () {
    priority_queue <Edge, vector <Edge>, cmp> pq;
    for (int i = 1; i <= n * 4; i ++) {
        L[i] = inf;
    }
    L[U] = 0;
    pq.push ({U, L[U]});
    while (!pq.empty ()) {
        auto [u, c] = pq.top ();
        pq.pop ();
        //cout << u << ' ' << c << '\n';
        if (c > L[u]) {
            continue;
        }
        for (auto [v, w] : g[u]) {
            if (L[v] > L[u] + w) {
                L[v] = L[u] + w;
                pq.push ({v, L[v]});
            }
        }
    }
}

int ts (int u, int t) {
    return u + t * n;
}

void solve () {
    cin >> n >> m >> S >> T >> U >> V;
    for (int i = 1; i <= m; i ++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back ({v, w});
        adj[v].push_back ({u, w});
    }
    dijkstraST ();
    int best = Ls[T];
    // dinh tien 4 chieu :
    // 0 : chua di vao duong S -> T
    // 1, 2 : dang di vao duong S -> T theo huong nguoc nhau
    // 3 : best khi di xong
    for (int u = 1; u <= n; u ++) {
        g[ts (u, 0)].push_back ({ts (u, 1), 0});
        g[ts (u, 0)].push_back ({ts (u, 2), 0});
        g[ts (u, 1)].push_back ({ts (u, 3), 0});
        g[ts (u, 2)].push_back ({ts (u, 3), 0});
        for (auto [v, w] : adj[u]) {
            if (Ls[u] + w + Lt[v] == best) {
                g[ts (u, 1)].push_back ({ts (v, 1), 0});
                g[ts (v, 2)].push_back ({ts (u, 2), 0});
            }
            g[ts (u, 0)].push_back ({ts (v, 0), w});
            g[ts (u, 3)].push_back ({ts (v, 3), w});
        }
    }
    dijkstraUV ();
    cout << L[ts (V, 3)] << '\n';
    // for (int i = 1; i <= n * 4; i ++) {
        // cout << L[i] << ' ';
        // if (i % n == 0) {
            // cout << '\n';
        // }
    // }
    return;
}

signed main () {
    cin.tie (nullptr) -> sync_with_stdio (false);
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    int t = 1;
    //cin >> t;
    while (t --) {
        solve ();
    } 
    return 0;
}
// thfdgb

Compilation message (stderr)

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

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