Submission #838945

#	Time	Username	Problem	Language	Result	Execution time	Memory
838945		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	2069 ms	262144 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 int inf = 1e9;
const int N = 1e5+5;

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

void dijkstra(int s, int 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) {
    for(int v:dag[u]) {
        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();

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

    save[t] = 1;
    dfs(s);
}

void dfs_dp(int u) {
    for(int v:tree[u]) {
        dfs_dp(v);
        dpv[u] = min(dpv[u], dpv[v]);
        dpu[u] = min(dpu[u], dpu[v]);
    }
    dpv[u] = min(dpv[u], dv[u]);
    dpu[u] = min(dpu[u], du[u]);

    ans = min(ans, dpv[u]+dpu[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:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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