Submission #1136123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136123		neowami	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	173 ms	20748 KiB

commuter_pass

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

#define ft first
#define sc second
#define int long long
using pii = pair<int, int>;
template<class T> using heapmin = priority_queue<T, vector<T>, greater<T>>;

const int N = 1e5 + 5;
const int inf = 1e17;
int n, m, s, t, u, v;
vector<pii> G[N];
int sdist[N], tdist[N], udist[N], vdist[N];
int min_dist_from_v_to_i_reliant_on_s[N], min_dist_from_v_to_i_reliant_on_t[N];
bool ckmin(int &u, int v) {
    if (u > v) return u = v, 1;
    return 0;
}
void dijkstra(int root, int dist[]) {
    for (int i = 1; i <= n; i++) dist[i] = inf;
    dist[root] = 0;
    heapmin<pii> Q;
    Q.push({0, root});
    while(!Q.empty()) {
        int old = Q.top().ft, u = Q.top().sc;
        Q.pop();
        if (old != dist[u]) continue;
        for (pii item: G[u]) {
            int w = item.ft + old, v = item.sc;
            if (ckmin(dist[v], w)) Q.push({dist[v], v});
        }
    }
}
void calc(int root, int dist[], const int cost[], int min_cost[], int tar) {
    for (int i = 1; i <= n; i++) dist[i] = min_cost[i] = inf;
    dist[root] = 0;
    heapmin<pii> Q;
    Q.push({0, root});
    min_cost[root] = cost[root];
    while(!Q.empty()) {
        int old = Q.top().ft, u = Q.top().sc;
        Q.pop();
        if (old != dist[u]) continue;
        if (u == tar) break;
        for (pii item: G[u]) {
            int w = item.ft + old, v = item.sc;
            if (ckmin(dist[v], w)) {
                Q.push({dist[v], v});
                min_cost[v] = min(min_cost[u], cost[v]);
            }
            else if (dist[v] == w) {
                min_cost[v] = min({min_cost[v], min_cost[u], cost[v]});
            }
        }
    }
} 
signed main() {
    cin.tie(NULL)->sync_with_stdio(false);
    if(ifstream("Input.inp")) {
        freopen("Input.inp", "r", stdin);
        freopen("Output.out", "w", stdout);
    }
    cin >> n >> m >> s >> t >> u >> v;
    for (int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        G[u].push_back({w, v});
        G[v].push_back({w, u});
    }
    dijkstra(u, udist);
    dijkstra(v, vdist);
    calc(s, sdist, vdist, min_dist_from_v_to_i_reliant_on_s, t);
    calc(t, tdist, vdist, min_dist_from_v_to_i_reliant_on_t, s);
    int ans = udist[v];
    for (int i = 1; i <= n; i++) {
        if (sdist[i] + tdist[i] == sdist[t]) {
            ans = min(ans, udist[i] + min(min_dist_from_v_to_i_reliant_on_s[i], min_dist_from_v_to_i_reliant_on_t[i]));
        }
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

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

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