Submission #1153062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153062		sunflower	Commuter Pass (JOI18_commuter_pass)	C++17	55 / 100	151 ms	16904 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;
    }
}

namespace subtask3 {
    bool check() {
        return (numNode <= 300);
    }

    ll dist[310][310];

    void solve() {
        // floyd algorithm;
        memset(dist, 0x3f, sizeof(dist));
        FOR(i, 1, numNode) dist[i][i] = 0;

        FOR(i, 1, numEdge) {
            int u = edges[i].u, v = edges[i].v, w = edges[i].w;
            minimize(dist[u][v], w);
            minimize(dist[v][u], w);
        }

        // process floyd;
        FOR(tmp, 1, numNode) {
            FOR(u, 1, numNode) FOR(v, u + 1, numNode) {
                minimize(dist[u][v], dist[u][tmp] + dist[tmp][v]);
                dist[v][u] = dist[u][v];
            }
        }

        ll res = dist[U][V];
        FOR(tmp_u, 1, numNode) {
            FOR(tmp_v, 1, numNode) {
                if (dist[S][tmp_u] + dist[tmp_u][tmp_v] + dist[tmp_v][T] == dist[S][T]) {
                    minimize(res, dist[U][tmp_u] + dist[V][tmp_v]);
                    minimize(res, dist[U][tmp_v] + dist[V][tmp_u]);
                }
            }
        }

        cout << res;
    }
}

namespace subtask2 {
    void solve() {
        vector <ll> sta_s = Dijkstra(S), sta_t = Dijkstra(T);
        FOR(i, 1, numNode) adj[i].clear();
        FOR(i, 1, numEdge) {
            int u = edges[i].u, v = edges[i].v, w = edges[i].w;
            if (min(sta_s[u] + sta_t[v], sta_s[v] + sta_t[u]) + w == sta_s[T]) w = 0;
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        }

        vector <ll> sta_u = Dijkstra(U);
        cout << sta_u[V]; // exchange V with T
    }
}

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;
    if (subtask3 :: check()) return subtask3 :: solve(), 0;
    subtask2 :: solve();

    return 0;
}

Compilation message (stderr)

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

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