Submission #948492

#	Time	Username	Problem	Language	Result	Execution time	Memory
948492		kornkin	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	247 ms	20168 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define pqpiig priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>
#define ll long long 

ll n, m, s, t, u, v, dis[100001], par[100001];
vector<pair<ll, ll>> g[100001];

int main(){
    ios_base::sync_with_stdio(0);

    cin >> n >> m >> s >> t >> u >> v;
    for(ll i = 0; i < m; i++){
        ll u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});

        par[i] = i;
    }

    memset(dis, 0x3f3f3f3f, sizeof(dis));

    pqpiig pq;
    pq.push({0, s});
    dis[s] = 0;
    while(!pq.empty()){
        ll now = pq.top().second;
        pq.pop();


        for(auto &[e, w] : g[now]){
            if(dis[e] > dis[now] + w){
                dis[e] = dis[now] + w;
                par[e] = now; 
                pq.push({dis[e], e});
            }
        }
    }

    for(ll i = par[t]; par[i] != i; i = par[i]) g[i].push_back({par[i], 0}), g[par[i]].push_back({i, 0});

    memset(dis, 0x3f3f3f3f, sizeof(dis));
    
    pq.push({0, u});
    dis[u] = 0;
    while(!pq.empty()){
        ll now = pq.top().second;
        pq.pop();


        for(auto &[e, w] : g[now]){
            if(dis[e] > dis[now] + w){
                dis[e] = dis[now] + w;
                par[e] = now; 
                pq.push({dis[e], e});
            }
        }
    }

    //for(ll i = 1; i <= n; i++) cout << i << ": " << dis[i] << '\n'; 

    cout << dis[v];

    return 0;
}

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