Submission #1224721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224721		nanaseyuzuki	Commuter Pass (JOI18_commuter_pass)	C++20	16 / 100	248 ms	28056 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define int long long
const int mn = 2e5 + 5, inf = 2e18;

int n, m, k, d[3][mn], dp[mn];  
vector <pii> a[mn], b[mn];

void dijkstra(int aa, int d[]){
    fill(d, d + mn, inf);
    d[aa] = 0;
    priority_queue <pii, vector <pii>, greater <pii>> pq;
    pq.push({d[aa], aa});
    while(pq.size()){
        int u = pq.top().se;
        int c = pq.top().fi;
        pq.pop();
        if(d[u] < c) continue;
        for(auto i : a[u]){
            int v = i.fi, w = i.se;
            if(d[v] > w + c){
                d[v] = w + c;
                // cout << aa << ' ' << d[v] << '\n';
                pq.push({d[v], v});
            }
        }
    }
}

void solve(){
    cin >> n >> m;
    int aa, bb, cc, dd; cin >> aa >> bb >> cc >> dd;
    vector <pair<pii, int>> edges;
    for(int i = 1; i <= m; i++){
        int u, v, c; cin >> u >> v >> c;
        a[u].push_back({v, c});
        a[v].push_back({u, c});
    }
    dijkstra(aa, d[1]);
    dijkstra(bb, d[2]);
    priority_queue <pii, vector <pii>, greater<pii>> pq;
    int path = d[1][bb];
    fill(dp, dp + mn, inf);
    dp[cc] = 0;
    pq.push({dp[cc], cc});
    while(pq.size()){
        int c, u;
        tie(c, u) = pq.top();
        pq.pop();
        if(c > dp[u]) continue;
        for(auto i : a[u]){
            int v = i.fi, w = i.se;
            if(d[1][u] + w + d[2][v] == path){
                if(dp[v] > dp[u]){
                    dp[v] = dp[u];
                    pq.push({dp[v], v});
                }
            }
            else{
                if(dp[v] > dp[u] + w){
                    dp[v] = dp[u] + w;
                    pq.push({dp[v], v});
                }
            }
        }
    }
    cout << dp[dd];
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if(fopen("tunnel.inp", "r")){
        freopen("tunnel.inp", "r", stdin);
        freopen("tunnel.out", "w", stdout);
    }
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}

Compilation message (stderr)

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

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