Submission #1224757

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224757		nanaseyuzuki	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	303 ms	37880 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 && !(c1 == 1 && c2 == 0) && !(c1 == 0 && c2 == 1)){
                if(dp[v][1][1] > dp[u][c1][c2]){
                    dp[v][1][1] = dp[u][c1][c2];
                    pq.push({{dp[v][1][1], v}, {1, 1}});
                }
            }
            else if(d[1][v] + w + d[2][u] == path && !(c1 == 1 && c2 == 1) && !(c1 == 0 && c2 == 1)){
                if(dp[v][1][0] > dp[u][c1][c2]){
                    dp[v][1][0] = dp[u][c1][c2];
                    pq.push({{dp[v][1][0], v}, {1, 0}});
                }
            }
            else if(c1 == 0 && c2 == 0){
                if(dp[v][0][0] > dp[u][c1][c2] + w){
                    dp[v][0][0] = dp[u][c1][c2] + w;
                    pq.push({{dp[v][0][0], v}, {0, 0}});
                }
            }
            else{
                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 << 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:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen("tunnel.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen("tunnel.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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