Submission #1226560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226560		wedonttalkanymore	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	111 ms	19436 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 = (ll)1e18;

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

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

void dijkstra1() {
    for (int i = 1; i <= n; i++) dist_ans[i] = INF;
    dist_ans[U] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, U});
    while (!q.empty()) {
        auto tmp = q.top(); q.pop();
        int u = tmp.se; 
        ll cost = tmp.fi;
        if (cost > dist_ans[u]) continue;
        for (auto &v : adj[u]) {
            int to = v.fi;
            int x = min(u, to), y = max(u, to);
            ll w = mp[{x,y}];
            if (dist_ans[to] > dist_ans[u] + w) {
                dist_ans[to] = dist_ans[u] + w;
                q.push({dist_ans[to], to});
            }
        }
    }
}

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]].emplace_back(b[i], c[i]);
        adj[b[i]].emplace_back(a[i], c[i]);
    }

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

    ll D = dist_s[T];
    for (int i = 1; i <= m; i++){
        int u = a[i], v = b[i];
        int x = min(u,v), y = max(u,v);
        if ((dist_s[u] + c[i] + dist_t[v] == D) ||
            (dist_s[v] + c[i] + dist_t[u] == D)) {
            mp[{x,y}] = 0;
        } else {
            mp[{x,y}] = 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