Submission #1283044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283044		anhphant	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	2096 ms	17452 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll N, M, S, T, U, V;
struct edge {
    ll v, w;
    edge() {
        v = w = 0;
    }
    edge(ll v_, ll w_) {
        v = v_;
        w = w_;
    }
};
vector<edge> GR[200007];
ll dist[200007], visited[200007], dist2[200007];
set<pair<ll, ll>> config;

ll dijsktra() {
    for(int i = 0; i <= N; ++i) {
        dist2[i] = 1e18;
        visited[i] = 0;
    }
    struct cmp {
        bool operator () (ll x1, ll x2) {
            return dist2[x1] > dist2[x2];
        }
    };
    priority_queue<ll, vector<ll>, cmp> heap;
    dist2[U] = 0;
    heap.push(U);
    while(!heap.empty()) {
        ll u = heap.top();
        heap.pop();
        if (visited[u]) continue;
        visited[u] = 1;
        for(auto tmp : GR[u]) {
            ll v = tmp.v;
            ll w = tmp.w;
            if (config.count({u, v}) || config.count({v, u})) w = 0;
            if (dist2[v] > dist2[u] + w) {
                dist2[v] = dist2[u] + w;
                heap.push(v);
            }
        }
    }
    return dist2[V];
}

int main() {
    ios_base :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0); cerr.tie(0);
    if (fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.ans", "w", stdout);
    }

    cin >> N >> M >> S >> T >> U >> V;
    for(int i = 1; i <= M; ++i) {
        ll u, v, c;
        cin >> u >> v >> c;
        GR[u].push_back(edge(v, c));
        GR[v].push_back(edge(u, c));
    }

    for(int i = 0; i <= N; ++i) dist[i] = 1e18;
    dist[S] = 0;
    struct cmp {
        bool operator () (ll x1, ll x2) {
            return dist[x1] > dist[x2];
        }
    };
    priority_queue<ll, vector<ll>, cmp> heap;
    heap.push(S);
    while(!heap.empty()) {
        ll u = heap.top();
        heap.pop();
        if (visited[u]) continue;
        visited[u] = 1;
        for(auto tmp : GR[u]) {
            ll v = tmp.v;
            ll w = tmp.w;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                heap.push(v);
            }
        }
    }

    //for(int i = 1; i <= N; ++i) cerr << dist[i] << " "; cerr << '\n';
    ll ans = 1e18;
    auto dfs = [&](auto&& self, ll u) {
        //cerr << u << " " << dist[u] << '\n';
        if (u == S) {
            ans = min(ans, dijsktra());
            return;
        }
        for(auto tmp : GR[u]) {
            ll v = tmp.v;
            ll w = tmp.w;
            if (dist[v] == dist[u] - w) {
                config.insert({u, v});
                self(self, v);
                config.erase({u, v});
            }
        }
    };

    dfs(dfs, T);
    cout << ans;
}

Compilation message (stderr)

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

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