Submission #1166029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166029		llogm	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	318 ms	60008 KiB

commuter_pass

#include <bits/stdc++.h>                                                                                                                                                                                      //Logm
using namespace std;
#define int long long
#define II pair<int,int>
#define fi first
#define se second

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

const int N = 1e5+5;
int n, m;
int S, T, U, V;
vector<II> adj[N];
vector<II> trace[N];

map<II, bool> dag;

int f[N];
void dijkstra1(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});
                trace[v.se].push_back(II(v.fi, u.se));
            }
            else if (f[v.se] == f[u.se] + v.fi) {
                trace[v.se].push_back(II(v.fi, u.se));
            }
        }
    }
}

vector<II> adj2[N];

void dijkstra2(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: adj2[u.se]) {
            if (mini(f[v.se], f[u.se] + v.fi)) {
                q.push({f[v.se], v.se});
            }
        }
    }
}

bool vis[N];

void dfs(int u) {
    vis[u] = 1;
    for (II x: trace[u]) {
        int v = x.se, w = x.fi;
        dag[II(v, u)] = 1;
        if (!vis[v])
            dfs(v);
    }
}

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;
    while (m--) {
        int u, v, c; cin >> u >> v >> c;
        adj[u].push_back(II(c, v));
        adj[v].push_back(II(c, u));
    }

    dijkstra1(S);

    dfs(T);

    // for (auto x: dag) {
    //     cout << x.fi.fi << ' ' << x.fi.se << '\n';
    // }
    for (int u = 1; u <= n; ++u) {
        for (II x: adj[u]) {
            int v = x.se, w = x.fi;
            if (dag[II(u, v)]) {
                adj2[u].push_back(II(0, v));
            }
            else adj2[u].push_back(II(w, v));
        }
    }

    dijkstra2(U);
    cout << f[V];
    return 0;
}

Compilation message (stderr)

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

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