Submission #833387

#	Time	Username	Problem	Language	Result	Execution time	Memory
833387		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	329 ms	23872 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];
ll d2[MAXN];
ll dcomp1[MAXN];
ll dcomp2[MAXN];
bool visited[MAXN];

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

    using pii = pair< 
                    pair<ll, ll>, 
                    pair<
                        pair<ll, ll>,
                        ll
                        > 
                    >;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push(
        {
            {
                0, dcomp1[s] + dcomp2[s]
            },
            {
                {dcomp1[s], dcomp2[s]},
                s
            }
        }
    );
    d[s] = 0;
    d2[s] = dcomp1[s] + dcomp2[s] ;
    while (!q.empty()) {
        ll v = q.top().second.second;
        ll d_v = q.top().first.first;
        ll dc1 = q.top().second.first.first;
        ll dc2 = q.top().second.first.second;
        ll dcsum = q.top().first.second;
        // cerr << d_v << " " << dcsum << " " << dc1 << " " << dc2 << " " << v << endl;
        q.pop();
        if (visited[v])
            continue;
        visited[v] = true;
        // cerr << v << endl;
        for (auto edge : adj[v]) {
            ll to = edge.first;
            ll len = edge.second;
            ll now_dc1 = min(dc1, min(dcomp1[v], dcomp1[to]));
            ll now_dc2 = min(dc2, min(dcomp2[v], dcomp2[to]));
            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                d2[to] = min(d2[to], now_dc1 + now_dc2);
                // q.push({d[to], to});
                q.push(
                    {
                        {
                            d[to], now_dc1 + now_dc2
                        },
                        {
                            {now_dc1, now_dc2},
                            to
                        }
                    }
                );
            }else if(d[v] + len == d[to]){
                if(now_dc1 + now_dc2 < d2[to]){
                    d2[to] = min(d2[to], now_dc1 + now_dc2);
                    q.push(
                        {
                            {
                                d[to], now_dc1 + now_dc2
                            },
                            {
                                {now_dc1, now_dc2},
                                to
                            }
                        }
                    );
                }
            }
        }
    }
}

void dijkstra_comp1(int s) {
    for(int i = 0; i < MAXN; i++){
        dcomp1[i] = LINF;
    }
    dcomp1[s] = 0;
    using pii = pair<ll, int>;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, s});
    while (!q.empty()) {
        int v = q.top().second;
        ll d_v = q.top().first;
        q.pop();
        if (d_v != dcomp1[v])
            continue;
        for (auto edge : adj[v]) {
            int to = edge.first;
            ll len = edge.second;
            if (dcomp1[v] + len < dcomp1[to]) {
                dcomp1[to] = dcomp1[v] + len;
                q.push({dcomp1[to], to});
            }
        }
    }
}
void dijkstra_comp2(int s) {
    for(int i = 0; i < MAXN; i++){
        dcomp2[i] = LINF;
    }
    dcomp2[s] = 0;
    using pii = pair<ll, int>;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, s});
    while (!q.empty()) {
        int v = q.top().second;
        ll d_v = q.top().first;
        q.pop();
        if (d_v != dcomp2[v])
            continue;
        for (auto edge : adj[v]) {
            int to = edge.first;
            ll len = edge.second;
            if (dcomp2[v] + len < dcomp2[to]) {
                dcomp2[to] = dcomp2[v] + len;
                q.push({dcomp2[to], to});
            }
        }
    }
}

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_comp1(comp1);
    dijkstra_comp2(comp2);

    dijkstra(ibukota1) ;
    // cerr << d[ibukota2] << endl;
    // cout << d2[ibukota2] << endl;
    ll ans = min(d2[ibukota2], dcomp1[comp2]);
    cout << ans << endl;
}

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

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(int)':
commuter_pass.cpp:48:12: warning: unused variable 'd_v' [-Wunused-variable]
   48 |         ll d_v = q.top().first.first;
      |            ^~~
commuter_pass.cpp:51:12: warning: unused variable 'dcsum' [-Wunused-variable]
   51 |         ll dcsum = q.top().first.second;
      |            ^~~~~

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