Submission #1226565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226565		wedonttalkanymore	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	126 ms	15304 KiB

commuter_pass

#include <bits/stdc++.h>
#define pii pair<long long, long long>
#define fi first
#define se second
using namespace std;
using ll = long long;

const int N = 100005;
const ll INF = 1e18;

int n, m, S, T, U, V;
vector<pair<int,int>> adj[N];
ll dist_s[N], dist_t[N], dist_ans[N];
int a[N], b[N], c[N];
ll costOnPass[N];

void dijkstra(int src, ll *length) {
    for (int i = 1; i <= n; i++) length[i] = INF;
    length[src] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > length[u]) continue;
        for (auto &ed : adj[u]) {
            int v = ed.fi, id = ed.se;
            ll w = c[id];
            if (length[v] > d + w) {
                length[v] = d + w;
                pq.push({length[v], v});
            }
        }
    }
}

void dijkstra1() {
    for (int i = 1; i <= n; i++) dist_ans[i] = INF;
    dist_ans[U] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, U});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist_ans[u]) continue;
        for (auto &ed : adj[u]) {
            int v = ed.fi, id = ed.se;
            ll w = costOnPass[id];
            if (dist_ans[v] > d + w) {
                dist_ans[v] = d + w;
                pq.push({dist_ans[v], v});
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> S >> T >> U >> V;
    for (int i = 1; i <= m; i++){
        cin >> a[i] >> b[i] >> c[i];
        adj[a[i]].push_back({b[i], i});
        adj[b[i]].push_back({a[i], i});
    }

    dijkstra(S, dist_s);
    dijkstra(T, dist_t);

    ll D = dist_s[T];
    for (int i = 1; i <= m; i++){
        // nếu (a→b) hoặc (b→a) nằm trên 1 đường ngắn nhất S→T
        if ((dist_s[a[i]] + c[i] + dist_t[b[i]] == D) ||
            (dist_s[b[i]] + c[i] + dist_t[a[i]] == D)) {
            costOnPass[i] = 0;
        } else {
            costOnPass[i] = c[i];
        }
    }

    dijkstra1();
    cout << dist_ans[V] << "\n";
    return 0;
}

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