Submission #1253818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253818		ducanh0811	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	341 ms	41092 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
using namespace std;

int n, m;
#define MAXN 200005
int S, T, U, V, ST;
vector<pair<int, int>> g[MAXN], adj[MAXN];
int d[MAXN][4];
int dp[MAXN][2];
bool vi[MAXN];
int res = 1e15;
vector<int> topo;

struct edge {
    int u, v, w;
};
vector<edge> edges;

void dijkstra(int s, int id){
    memset(vi, false, sizeof vi);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, s));
    d[s][id] = 0;
    while (pq.size()){
        int w, u; tie(w, u) = pq.top();
        pq.pop();
        if (vi[u]) continue;
        vi[u] = 1;
        for (pair<int, int> &x : g[u]){
            int v, ww; tie(v, ww) = x;
            if (d[v][id] > w + ww){
                d[v][id] = w + ww;
                pq.push(make_pair(d[v][id], v));
            }
        }
    }
}

void dfs(int u){
    vi[u] = 1;
    for (pair<int, int> &x : g[u]){
        int v, w; tie(v, w) = x;
        if (vi[v] || d[u][0] + w + d[v][1] != ST) continue;
        dfs(v);
    }
    topo.push_back(u);
}

void solve(){
    memset(d, 0x3f, sizeof d);
    cin >> n >> m >> S >> T >> U >> V;
    FOR(i, 1, m){
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back(make_pair(v, w));
        g[v].push_back(make_pair(u, w));
        edges.push_back({u, v, w});
    }
    dijkstra(S, 0);
    dijkstra(T, 1);
    dijkstra(U, 2);
    dijkstra(V, 3);
    ST = d[T][0];
    res = d[V][2];
    FOR(i, 1, n){
        dp[i][0] = d[i][2];
        dp[i][1] = d[i][3];
    }
    memset(vi, false, sizeof vi);
    dfs(S);
    reverse(topo.begin(), topo.end());
    for (int &u : topo){
        for (pair<int, int> &x : g[u]){
            int v, w; tie(v, w) = x;
            if (d[u][0] + w + d[v][1] != ST) continue;
            dp[v][0] = min(dp[v][0], dp[u][0]);
            dp[v][1] = min(dp[v][1], dp[u][1]);
        }
    }
    FOR(i, 1, n){
        if (d[i][0] + d[i][1] != ST) continue;
        res = min({res, d[i][2] + dp[i][1], dp[i][0] + d[i][3]});
    }
    cout << res;
}

/**
6 6
1 6
3 4
1 2 1
2 3 1
3 5 1
2 4 1
4 5 1
5 6 1

6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1

**/

#define task "PATH"
int32_t main(){
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    solve();
    return 0;
}

Compilation message (stderr)

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

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