Submission #1166324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166324		merciless_lassie	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	582 ms	109016 KiB

commuter_pass

#include "bits/stdc++.h"
using namespace std;
#define int long long
const int N = 1e6 + 5;
#define II pair<int,int>
#define fi first
#define se second

int n, m, s, t, U, V;
int f[N], f2[N];
vector<II> adj[N], adj2[N];
map<II, bool> mp; // Đánh dấu cạnh thuộc shortest path

template<class X, class Y> bool mini(X& x, const Y y) {
    if (x > y) return x = y, 1;
    return 0;
}

// Dijkstra để tìm đường đi ngắn nhất từ `s`
void dijkstra(int node) {
    memset(f, 0x3f, sizeof f);
    priority_queue<II, vector<II>, greater<II>> q;
    q.push({0, node});
    f[node] = 0;

    while (!q.empty()) {
        II u = q.top(); q.pop();
        if (u.fi != f[u.se]) continue;

        for (II v: adj[u.se]) {
            if (mini(f[v.se], f[u.se] + v.fi)) {
                q.push({f[v.se], v.se});
                mp[{u.se, v.se}] = 1;
                mp[{v.se, u.se}] = 1; // Đồ thị vô hướng
            } 
            else if (f[v.se] == f[u.se] + v.fi) {
                mp[{u.se, v.se}] = 1;
                mp[{v.se, u.se}] = 1;
            }
        }
    }
}

// Xây dựng `adj2` dựa trên shortest path từ `s → t`
void build_adj2() {
    for (int i = 1; i <= n; i++) {
        for (II j : adj[i]) {
            if (mp[{i, j.se}]) { 
                adj2[i].push_back({0, j.se});  // Nếu thuộc đường đi `s → t` thì cost = 0
            } else {
                adj2[i].push_back(j);  // Cạnh không thuộc đường đi giữ nguyên
            }
        }
    }
}

// Dijkstra từ `U` trên đồ thị `adj2`
void dijkstra2(int node) {
    memset(f2, 0x3f, sizeof f2);
    priority_queue<II, vector<II>, greater<II>> q;
    q.push({0, node});
    f2[node] = 0;

    while (!q.empty()) {
        II u = q.top(); q.pop();
        if (u.fi != f2[u.se]) continue;

        for (II v: adj2[u.se]) {
            if (mini(f2[v.se], f2[u.se] + v.fi)) {
                q.push({f2[v.se], v.se});
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    if (fopen("_ab.inp", "r")) {
        freopen("_ab.inp", "r", stdin);
        freopen("_ab.out", "w", stdout);
    }

    cin >> n >> m; 
    cin >> s >> t >> U >> V;
    
    for (int i = 1; i <= m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back({c, v});
        adj[v].push_back({c, u});
    }

    dijkstra(s);  // Tìm shortest path từ `s`
    build_adj2(); // Xây đồ thị `adj2`
    dijkstra2(U); // Tìm đường từ `U` đến `V` trên `adj2`

    cout << f2[V] << "\n";
}

Compilation message (stderr)

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

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