Submission #833294

#	Time	Username	Problem	Language	Result	Execution time	Memory
833294		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	309 ms	17704 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long int

using namespace std;

const int MAXN = 1e5 + 10;
const int INF = INT_MAX;
const long long LINF = LLONG_MAX;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;

vector<pair<int, ll>> adj[MAXN];
ll d[MAXN];
vector<int> nodes;
int p[MAXN];

int reall[MAXN];

void dijkstra(int s) {
    for(int i = 0; i < MAXN; i++){
        d[i] = LINF;
    }

    using pii = pair<ll, int>;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, s});
    d[s] = 0;
    p[s] = -1;
    while (!q.empty()) {
        int v = q.top().second;
        ll d_v = q.top().first;
        q.pop();
        if (d_v != d[v])
            continue;
        // cerr << v << endl;
        for (auto edge : adj[v]) {
            int to = edge.first;
            ll len = edge.second;
            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                p[to] = v;
                q.push({d[to], to});
            }
        }
    }
}

void dijkstra2(int s) {
    for(int i = 0; i < MAXN; i++){
        d[i] = LINF;
    }

    using pii = pair<ll, int>;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, s});
    d[s] = 0;
    while (!q.empty()) {
        int v = q.top().second;
        ll d_v = q.top().first;
        q.pop();
        if (d_v != d[v])
            continue;
        if(reall[v] == 0){
            d[0] = min(d[0], d_v);
        }
        // cerr << v << " " << d[v] << endl;
        for (auto edge : adj[v]) {
            int to = edge.first;
            ll len = edge.second;
            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                q.push({d[to], to});
                // cerr << v << " " << to << " " << d[to] << endl;
            }
        }
    }
}

void solv(){
    int n, m;
    cin >> n >> m;
    int ibukota1, ibukota2;
    cin >> ibukota1 >> ibukota2;
    int comp1, comp2;
    cin >> comp1 >> comp2;
    for(int i = 0; i < m; i++){
        ll u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    dijkstra(ibukota1);
    
    for(int i = 1; i <= n; i++){
        reall[i] = i;
    }
    // queue<int> q;
    // q.push(ibukota2);
    // while(!q.empty()){
    //     int u = q.front();
    //     // cerr << u << " : ";
    //     q.pop();
    //     reall[u] = 0;
    //     for(auto i : p[u]){
    //         // cerr << i << " ";
    //         q.push(i);
    //     }
    //     // cerr << endl;
    // }
    // cerr << d[ibukot/a2] << endl;
    int now = ibukota2;
    while(now != -1){
        reall[now] = 0;
        now = p[now];
    }

    dijkstra2(comp1);
    long long ans = d[reall[comp2]];
    // cout << d[reall[comp2]] << endl;
    long long temp = d[0];
    // cout << d[0] << endl;
    dijkstra2(comp2);
    // cout << d[0] << endl;
    temp += d[0];
    ans = min(ans , temp);
    cout << ans << endl;

}

int main(){
    int tc = 1;
//    cin >> tc;
    while(tc--)solv();
    return 0;
}

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