Submission #1253238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253238		ducanh0811	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	260 ms	32888 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;
vector<pair<int, int>> g[MAXN], adj[MAXN];
int d[MAXN][2];
int dist[MAXN];
bool vi[MAXN];
int res = 1e15;

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 process(int s, int e){
    memset(vi, false, sizeof vi);
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, s));
    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 : adj[u]){
            int v, ww; tie(v, ww) = x;
            if (dist[v] > w + ww){
                dist[v] = w + ww;
                pq.push(make_pair(dist[v], v));
            }
        }
        for (pair<int, int> &x : g[u]){
            int v, ww; tie(v, ww) = x;
            if (dist[v] > w + ww){
                dist[v] = w + ww;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
    res = min(res, dist[e]);
}

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);
    int ST = d[T][0];
    for (edge &x : edges) {
        if (d[x.u][0] + x.w + d[x.v][1] == ST) adj[x.u].push_back(make_pair(x.v, 0));
    }
    process(U, V);
    process(V, U);
    FOR(i, 1, n) adj[i].clear();
    for (edge &x : edges) {
        if (d[x.v][0] + x.w + d[x.u][1] == ST) adj[x.v].push_back(make_pair(x.u, 0));
    }
    process(U, V);
    process(V, U);
    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
**/

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

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