Submission #1269723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269723		thanhlhp	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	321 ms	34596 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define iii pair<int, ii>
#define iiii pair<ii,ii>
#define fi first
#define se second
#define inf 10000000000000000
#define pi M_PI
const int N = 1e5 + 5;
int n, m;
int S, T, X, Y;
vector<ii> g[N];
int dx[N], dn[N];
vector<ii> g2[N], g3[N];
vector<iii> canh;
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen("main.inp","r")) {
        freopen("main.inp", "r", stdin);
        freopen("main.out", "w", stdout);
    }
    cin >> n >> m;
    cin >> S >> T >> X >> Y;
    for(int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({w,v});
        g[v].push_back({w,u});
        canh.push_back({w,{u,v}});
    }


    priority_queue<ii,vector<ii>,greater<ii>> pq;
    for(int i = 1; i <= n; i++) dx[i] = inf;
    dx[S] = 0;
    pq.push({0,S});
    while(pq.size()) {
        int u = pq.top().se;
        int du = pq.top().fi;
        pq.pop();
        if(du != dx[u]) continue;
        for(auto tmp : g[u]) {
            int v = tmp.se;
            int w = tmp.fi;
            if(dx[v] > dx[u] + w) {
                dx[v] = dx[u] + w;
                pq.push({dx[v],v});
            }
        }
    }

    for(int i = 1; i <= n; i++) dn[i] = inf;
    dn[T] = 0;
    pq.push({0,T});
    while(pq.size()) {
        int u = pq.top().se;
        int du = pq.top().fi;
        pq.pop();
        if(du != dn[u]) continue;
        for(auto tmp : g[u]) {
            int v = tmp.se;
            int w = tmp.fi;
            if(dn[v] > dn[u] + w) {
                dn[v] = dn[u] + w;
                pq.push({dn[v],v});
            }
        }
    }

    for(auto x : canh) {
            int i = x.se.fi;
            int j = x.se.se;
            int w = x.fi;

                //cout << i << ' ' << j << ' ' << w << '\n';
                if(dx[i] + w + dn[j] == dx[T]) {

                    g3[i].push_back({0,j});
                }
                if(dx[j] + w + dn[i] == dx[T]) {

                    g3[j].push_back({0,i});
                }


    }
//    for(int i = 1; i <= n; i++) {
//        for(auto tmp : g2[i]) {
//            cout << i << ' ' << tmp.se << ' ' << tmp.fi << '\n';
//        }
//    }
    for(auto tmp : canh) {
            int i = tmp.se.fi;
            int j = tmp.se.se;
            int w = tmp.fi;

                g3[i].push_back({w,j});


                g3[j].push_back({w,i});


    }

    for(int i = 1; i <= n; i++) dx[i] = inf;
    dx[X] = 0;
    pq.push({0,X});
    while(pq.size()) {
        int u = pq.top().se;
        int du = pq.top().fi;
        pq.pop();
        if(du != dx[u]) continue;
        for(auto tmp : g3[u]) {
            int v = tmp.se;
            int w = tmp.fi;
            if(dx[v] > dx[u] + w) {
                dx[v] = dx[u] + w;
                pq.push({dx[v],v});
            }
        }
    }
    int ans = dx[Y];
    for(int i = 1; i <= n; i++) dx[i] = inf;
    dx[Y] = 0;
    pq.push({0,Y});
    while(pq.size()) {
        int u = pq.top().se;
        int du = pq.top().fi;
        pq.pop();
        if(du != dx[u]) continue;
        for(auto tmp : g3[u]) {
            int v = tmp.se;
            int w = tmp.fi;
            if(dx[v] > dx[u] + w) {
                dx[v] = dx[u] + w;
                pq.push({dx[v],v});
            }
        }
    }
    ans = min(ans,dx[X]);
    cout << ans;
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen("main.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen("main.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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