Submission #575307

#	Time	Username	Problem	Language	Result	Execution time	Memory
575307		jtnydv25	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	382 ms	23092 KiB

commuter_pass

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

#define ll long long
#define pii pair<int, int>
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())

#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#define endl "\n" // remove in interactive
#endif

template<class T>
struct weighted_graph{
    vector<vector<pair<int, T>>> adj;
    int n;
    weighted_graph(){}
    weighted_graph(int n) : n(n), adj(n){}
    void add_edge(int a, int b, T w){
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    vector<T> distances(int s){
        vector<T> dist(n, numeric_limits<T>::max() / 2);
        priority_queue<pair<T, int>,vector<pair<T, int>>, greater<pair<T, int>> > Q; 
        dist[s] = 0;
        Q.push(pair<T, int>(0,s));
        while(!Q.empty()) {
            pair<T, int> top = Q.top();
            Q.pop();
            T d = top.first;
            int v = top.second;
            if(d <= dist[v]) {
                for(auto it : adj[v]){
                    int v2 = it.first;
                    T cost = it.second;
                    if(dist[v2] > dist[v] + cost) {
                        dist[v2] = dist[v] + cost;
                        Q.push(pair<T, int>(dist[v2], v2));
                    }
                }
            }
        }
        return dist;
    }
};

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n, m;
    cin >> n >> m;

    int S, T, U, V;
    cin >> S >> T >> U >> V;
    S--; T--; U--; V--;

    weighted_graph<ll> G(n);

    for(int i = 0; i < m; i++){
        int u, v, w; cin >> u >> v >> w;
        u--; v--;
        G.add_edge(u, v, w);
    }

    vector<ll> Dist_S = G.distances(S); // distances from S
    vector<ll> Dist_T = G.distances(T); // from T
    vector<ll> Dist_U = G.distances(U); // from U
    vector<ll> Dist_V = G.distances(V); // from V

    vector<int> vertices(n);
    iota(vertices.begin(), vertices.end(), 0);

    // sort according to distance from S
    sort(vertices.begin(), vertices.end(), [&](int i, int j){return Dist_S[i] < Dist_S[j];});

    ll ans = Dist_U[V];

    for(int i = 0; i < 2; i++){
        vector<ll> dp(n, 1LL << 60);
        // dp[v] = min dist(u, U) over all u that lie on some S-v shortest path.
        for(int v: vertices){
            dp[v] = Dist_U[v];
            for(auto it: G.adj[v]){
                int x = it.first;
                if(Dist_S[x] + it.second == Dist_S[v]){
                    dp[v] = min(dp[v], dp[x]);
                }
            }
        }
        for(int v = 0; v < n; v++) if(Dist_S[v] + Dist_T[v] == Dist_S[T]){
            ans = min(ans, Dist_V[v] + dp[v]);
        }

        swap(U, V);
        swap(Dist_U, Dist_V);
    }
    cout << ans << endl;
}

Compilation message (stderr)

commuter_pass.cpp: In instantiation of 'weighted_graph<T>::weighted_graph(int) [with T = long long int]':
commuter_pass.cpp:62:27:   required from here
commuter_pass.cpp:19:9: warning: 'weighted_graph<long long int>::n' will be initialized after [-Wreorder]
   19 |     int n;
      |         ^
commuter_pass.cpp:18:34: warning:   'std::vector<std::vector<std::pair<int, long long int>, std::allocator<std::pair<int, long long int> > >, std::allocator<std::vector<std::pair<int, long long int>, std::allocator<std::pair<int, long long int> > > > > weighted_graph<long long int>::adj' [-Wreorder]
   18 |     vector<vector<pair<int, T>>> adj;
      |                                  ^~~
commuter_pass.cpp:21:5: warning:   when initialized here [-Wreorder]
   21 |     weighted_graph(int n) : n(n), adj(n){}
      |     ^~~~~~~~~~~~~~

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