Submission #1224789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224789		nanaseyuzuki	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	379 ms	37988 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][2][2];  
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;
                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 <pair<pii, pii>, vector <pair<pii, pii>>, greater<pair<pii, pii>>> pq;
    int path = d[1][bb];
    fill(&dp[0][0][0], &dp[0][0][0] + mn * 2 * 2, inf);
    dp[cc][0][0] = 0;
    pq.push({{dp[cc][0][0], cc}, {0, 0}});
    while(pq.size()){
    int c, u, c1, c2;
    tie(c, u) = pq.top().fi, tie(c1, c2) = pq.top().se;
    pq.pop();
    if(c > dp[u][c1][c2]) continue;
    for(auto i : a[u]){
        int v = i.fi, w = i.se;
        if(d[1][u] + w + d[2][v] == path){
            if(c1 == 1 && c2 == 0){
                if(dp[v][1][0] > dp[u][1][0]){
                    dp[v][1][0] = dp[u][1][0];
                    pq.push({{dp[v][1][0], v}, {1, 0}});
                }
            }
            else if(c1 == 0 && c2 == 0){
                if(dp[v][1][0] > dp[u][0][0]){
                    dp[v][1][0] = dp[u][0][0];
                    pq.push({{dp[v][1][0], v}, {1, 0}});
                }
            }
        }
        else if(d[1][v] + w + d[2][u] == path){
            if(c1 == 1 && c2 == 1){
                if(dp[v][1][1] > dp[u][1][1]){
                    dp[v][1][1] = dp[u][1][1];
                    pq.push({{dp[v][1][1], v}, {1, 1}});
                }
            }
            else if(c1 == 0 && c2 == 0){
                if(dp[v][1][1] > dp[u][0][0]){
                    dp[v][1][1] = dp[u][0][0];
                    pq.push({{dp[v][1][1], v}, {1, 1}});
                }
            }
        }
        if(c1 == 0 && dp[v][c1][c2] > dp[u][c1][c2] + w){
            dp[v][c1][c2] = dp[u][c1][c2] + w;
            pq.push({{dp[v][c1][c2], v}, {c1, c2}});
        }
        if((c1 == 1 && c2 == 0) || (c1 == 1 && c2 == 1)){
            if(dp[v][0][1] > dp[u][c1][c2] + w){
                dp[v][0][1] = dp[u][c1][c2] + w;
                pq.push({{dp[v][0][1], v}, {0, 1}});
            }
        }
    }
}
    // cout << dp[dd][0][1] << '\n';
    cout << min({dp[dd][0][0], dp[dd][1][0], dp[dd][1][1], dp[dd][0][1]});
}

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:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen("tunnel.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen("tunnel.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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