Submission #1037190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037190		ThommyDB	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	285 ms	25664 KiB

commuter_pass

#include<bits/stdc++.h>

using namespace std;
#define int long long

int n, m, s, t, u, v, ans;
vector<vector<pair<int, int>>> adj;

vector<int> dist_u, dist_v;
vector<bool> visited;

void get_dist(int start, vector<int>& dist){
    dist.resize(n+1, 1e18);
    dist[start]=0;
    fill(visited.begin(), visited.end(), false);
    priority_queue<pair<int, int>> pq;
    pq.push({dist[start], start});
    while(!pq.empty()){
        int a = pq.top().second;
        int c = -pq.top().first;
        pq.pop();
        if(visited[a])continue;
        visited[a]=true;
        for(auto x : adj[a]){
            if(dist[a]+x.second < dist[x.first]){
                dist[x.first] = dist[a]+x.second;
                pq.push({-dist[x.first], x.first});
            }
        }
    }
}

signed main(){
    cin >> n >> m >> s >> t >> u >> v;
    adj.resize(n+1);
    visited.resize(n+1);
    
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    get_dist(u, dist_u);
    get_dist(v, dist_v);
    ans = dist_u[v];
    int a = s, b=t;
    for(int o = 0; o < 2; o++){
    vector<int> dist_a, dp_c, dp_d;
    dist_a.resize(n+1, 1e18);
    dp_c.resize(n+1, 1e18);
    dp_d.resize(n+1, 1e18);
    dist_a[a]=0;
    fill(visited.begin(), visited.end(), false);
    priority_queue<pair<int, pair<int, int>>> pq;
    pq.push({0, {a, 0}});
    while (!pq.empty())
    {
        int c = -pq.top().first;
        int d = pq.top().second.first;
        int e = pq.top().second.second;
        pq.pop();
        if(!visited[d]){
            visited[d]=true;
            dp_c[d]=min(dp_c[e],dist_u[d]);
            dp_d[d]=min(dp_d[e],dist_v[d]);
            for(auto x : adj[d]){
                if(dist_a[d] + x.second <= dist_a[x.first]){
                    dist_a[x.first]=dist_a[d]+x.second;
                    pq.push({-dist_a[x.first], {x.first, d}});
                }
            }
        }
        else{
            if(c==dist_a[d] && (min(dp_c[e],dist_u[d]) + min(dp_d[e], dist_v[d]) <= dp_c[d]+dp_d[d])){
                dp_c[d]=min(dp_c[e],dist_u[d]);
                dp_d[d]=min(dp_d[e], dist_v[d]);
            }
        }
    }
    ans = min(ans, dp_c[b] + dp_d[b]);
    a=t;b=s;
    }
    cout << ans << "\n";
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void get_dist(long long int, std::vector<long long int>&)':
commuter_pass.cpp:20:13: warning: unused variable 'c' [-Wunused-variable]
   20 |         int c = -pq.top().first;
      |             ^

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