Submission #839059

#	Time	Username	Problem	Language	Result	Execution time	Memory
839059		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	196 ms	30776 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define fi first
#define se second
using ll = long long;

const ll inf = 1e18;
const int N = 1e5+5;

int n, m, s, t, u, v;
ll ds[N], du[N], dv[N], dpv[N], dpu[N], save[N], ans = inf;
bool chk[N];
vector <int> dag[N], tree[N];
vector <pii> g[N];

void dijkstra(int s, ll d[]) {
    priority_queue <pii, vector<pii>, greater<pii>> pq;

    d[s] = 0;
    pq.push(make_pair(d[s], s));
    
    while(pq.size()) {
        pii u = pq.top(); pq.pop();
        if(u.fi > d[u.se]) continue;

        for(pii e:g[u.se]) {
            if(d[e.fi] > d[u.se] + e.se) {
                d[e.fi] = d[u.se] + e.se;
                pq.push(make_pair(d[e.fi], e.fi));
            }
        }
    }
}

void dfs(int u) {
    chk[u] = true;
    for(int v:dag[u]) if(!chk[v]) {
        dfs(v);
        if(save[v]) tree[u].emplace_back(v); 
        save[u] = save[u] | save[v];    
    }
}

void dag_dijkstra() {
    queue <int> q;
    q.push(s);

    while(q.size()) {
        int u = q.front(); q.pop();

        if(chk[u]) continue;
        chk[u] = true;

        for(pii e:g[u]) {
            if(ds[e.fi] == ds[u] + e.se) {
                dag[u].emplace_back(e.fi);
                q.push(e.fi);
            }
        }
    }

    memset(chk, 0, sizeof(chk));
    save[t] = 1;
    dfs(s);
}

void dfs_dp(int u) { 
    ll Minu = inf, Minv = inf;
    for(int v:tree[u]) {
        dfs_dp(v);
        ans = min({ans, du[u] + dpv[v], dv[u] + dpu[v]});
        Minu = min(Minu, dpu[v]);
        Minv = min(Minv, dpv[v]);
    }

    dpu[u] = min(Minu, du[u]); dpv[u] = min(Minv, dv[u]);
}

void dynamic_programming() {
    dfs_dp(s);
    ans = min(ans, du[v]);
    cout << ans;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if(fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }

    cin >> n >> m >> s >> t >> u >> v;

    for(int i = 1, a, b, c; i <= m; ++i) {
        cin >> a >> b >> c;
        g[a].emplace_back(b, c);
        g[b].emplace_back(a, c);
    }
    
    memset(ds, 0x3f, sizeof(ds)); memset(du, 0x3f, sizeof(du)); memset(dv, 0x3f, sizeof(dv));
    memset(dpv, 0x3f, sizeof(dpv)); memset(dpu, 0x3f, sizeof(dpu)); 
    dijkstra(s, ds); dijkstra(u, du), dijkstra(v, dv);

    dag_dijkstra();
    dynamic_programming();
}

Compilation message (stderr)

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

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