Submission #678547

#	Time	Username	Problem	Language	Result	Execution time	Memory
678547		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	531 ms	26700 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<pair<int, ll>>> g;
vector<ll> dijkstra(int s){
    vector<ll> result(g.size(), LLONG_MAX);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    result[s] = 0;
    pq.emplace(0, s);
    while (pq.size()){
        pair<ll, int> r = pq.top(); pq.pop();
        if (result[r.second] != r.first) continue;
        for (pair<int, ll> e: g[r.second]){
            ll dist = e.second + r.first;
            if (dist >= result[e.first]) continue;
            result[e.first] = dist;
            pq.emplace(dist, e.first);
        }
    }
    return result;
}
vector<pair<ll, ll>> dijkstra(int s, const vector<ll> &udist){
    vector<pair<ll, ll>> result(g.size(), make_pair(LLONG_MAX, LLONG_MAX));
    priority_queue<pair<pair<ll, ll>, int>, vector<pair<pair<ll, ll>, int>>, greater<>> pq;
    pq.emplace(make_pair(0, LLONG_MAX), s);
    result[s] = make_pair(0, LLONG_MAX);
    while (pq.size()){
        pair<pair<ll, ll>, int> r = pq.top(); pq.pop();
        if (result[r.second] != r.first) continue;
        r.first.second = result[r.second].second = min(r.first.second, udist[r.second]);
        for (pair<int, ll> e: g[r.second]){
            pair<ll, ll> dist(r.first.first + e.second, r.first.second);
            if (dist >= result[e.first]) continue;
            result[e.first] = dist;
            pq.emplace(dist, e.first);
        }
    }
    return result;
}
ll solve(const vector<pair<ll, ll>> &a, const vector<pair<ll, ll>> &b, ll st){
    ll min_result = LLONG_MAX;
    for (int i=0; i<a.size(); i++){
        if (a[i].first + b[i].first != st) continue;
        min_result = min(min_result, a[i].second + b[i].second);
    }
    return min_result;
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, m; cin >> n >> m;
    int s, t, u, v; cin >> s >> t >> u >> v;
    s--, t--, u--, v--;
    g.resize(n);
    for (int i=0; i<m; i++){
        int a, b, c; cin >> a >> b >> c;
        a--, b--;
        g[a].emplace_back(b, c);
        g[b].emplace_back(a, c);
    }
    vector<ll> fu = dijkstra(u), fv = dijkstra(v);
    ll st = dijkstra(s)[t];
    ll suvt = solve(dijkstra(s, fu), dijkstra(t, fv), st);
    ll svut = solve(dijkstra(s, fv), dijkstra(t, fu), st);
    ll uv = dijkstra(u)[v];
    cout << min({suvt, svut, uv}) << "\n";
}

Compilation message (stderr)

commuter_pass.cpp: In function 'll solve(const std::vector<std::pair<long long int, long long int> >&, const std::vector<std::pair<long long int, long long int> >&, ll)':
commuter_pass.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i=0; i<a.size(); i++){
      |                   ~^~~~~~~~~

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