Submission #1153039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153039		sunflower	Commuter Pass (JOI18_commuter_pass)	C++17	16 / 100	133 ms	17100 KiB

commuter_pass

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

#define ll long long
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define debug(x) cout << "[" << #x << " = " << (x) << "]" << endl

#define fi first
#define se second

typedef pair <long long, int> pli;

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

const long long INF = (long long) 1e18 + 7;

int numNode, numEdge, S, T, U, V;

#define MAX_EDGE 200'200
struct Edge {
    int u, v, w;
    Edge(int _u = 0, int _v = 0, int _w = 0) {
        u = _u, v = _v, w = _w;
    }
    void input() {
        cin >> u >> v >> w;
    }
} edges[MAX_EDGE + 2];

#define MAX_NODE 100'100
vector <pair <int, int>> adj[MAX_NODE + 2];

vector <ll> Dijkstra(int s) {
    vector <ll> dist(numNode + 2, INF);
    dist[s] = 0;

    priority_queue <pli, vector <pli>, greater <pli>> q;
    #define PUSH(s) q.push({dist[s], s})

    PUSH(s);

    while (!q.empty()) {
        ll cost = q.top().fi;
        int u = q.top().se;
        q.pop();

        if (cost > dist[u]) continue;

        for (const pair <int, int> &e : adj[u]) {
            int v = e.fi, w = e.se;
            if (minimize(dist[v], dist[u] + w)) {
                PUSH(v);
            }
        }
    }

    return dist;
}

namespace subtask1 {
    bool check() {
        return (S == U);
    }

    void solve() {
        vector <ll> sta_s = Dijkstra(S), sta_t = Dijkstra(T);
        vector <ll> sta_v = Dijkstra(V);

        ll res = sta_v[U];

        FOR(tmp, 1, numNode) {
            if (sta_s[tmp] + sta_t[tmp] == sta_s[T]) minimize(res, sta_v[tmp]);
        }

        cout << res;
    }
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    if (fopen("test.inp","r")) {
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }

    cin >> numNode >> numEdge;
    cin >> S >> T;
    cin >> U >> V;
    FOR(i, 1, numEdge) {
        edges[i].input();
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    if (subtask1 :: check()) return subtask1 :: solve(), 0;

    return 0;
}

Compilation message (stderr)

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

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