Submission #1082875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082875		bundaunuoctuong	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	2073 ms	183424 KiB

commuter_pass

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define mod 1000000007
#define ull unsigned long long
#define mll map<int,int>
#define vll vector<int>
#define pll pair<int, int>
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define FOR1(i, a, b) for(int i = a; i <= b; i++)
#define UNF(i, a, b) for(int i = b; i >= a; i--)
#define UNF1(i, a, b) for(int i = b; i > a; i--)
#define ll long long
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define name "QUADQUERY"
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int MAXN = 3e6 + 5;

int n, m, s, t, x, y;
vector<pll> g[MAXN];
ll d[MAXN], ans = LLONG_MAX;
map<pll, bool> check;
vector<int> edge[MAXN];

void Dijkstra(int p, int end) {
    fill(d, d + n + 1, LLONG_MAX);
    d[p] = 0;
    priority_queue<pll, vector<pll>, greater<pll>> q;
    q.push(mp(d[p], p));
    while (!q.empty()) {
        int u = q.top().Y, cost = q.top().X;
        q.pop();
        if (cost > d[u]) continue;
        if (u == end) break;
        for (const auto& x : g[u]) {
            if (d[x.X] > d[u] + x.Y) {
                d[x.X] = d[u] + x.Y;
                q.push(mp(d[x.X], x.X));
                edge[x.X].clear();
            }
            if (d[x.X] == d[u] + x.Y) edge[x.X].pb(u);
        }
    }
}

void Dijkstra2(int p, int end) {
    fill(d, d + n + 1, LLONG_MAX);
    d[p] = 0;
    priority_queue<pll, vector<pll>, greater<pll>> q;
    q.push(mp(d[p], p));
    while (!q.empty()) {
        int u = q.top().Y, cost = q.top().X;
        q.pop();
        if (cost > d[u]) continue;
        if (u == end) break;
        for (const auto& x : g[u]) {
            ll val = check[{u, x.X}] ? 0 : x.Y;
            if (d[x.X] > d[u] + val) {
                d[x.X] = d[u] + val;
                q.push(mp(d[x.X], x.X));
            }
        }
    }
}

void DFS(int u, int end) {
    if (u == end) {
        Dijkstra2(x, y);
        ans = min(ans, d[y]);
    }
    for (const int& v : edge[u]) {
        check[{u, v}] = check[{v, u}] = true;
        DFS(v, end);
        check[{u, v}] = check[{v, u}] = false;
    }
}

void solve() {
    Dijkstra(s, t);
    DFS(t, s);
    cout << ans;
}

int main() {
    fast;
    if (fopen(name".inp", "r")) {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }
    cin >> n >> m >> s >> t >> x >> y;
    FOR1(i, 1, m) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].pb(mp(v, w));
        g[v].pb(mp(u, w));
    }
    solve();
    return 0;
}

Compilation message (stderr)

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

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