Submission #849547

#	Time	Username	Problem	Language	Result	Execution time	Memory
849547		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	457 ms	31480 KiB

commuter_pass

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

#define NMAX 100000
#define f first
#define s second
int N, M, S, T, U, V;
vector<pair<long long, int> > E[NMAX + 5];
long long res;
class state {
public:
    int u;
    long long d;
    bool t1, t2;
    state() {
        u = 0;
        d = 0;
        t1 = t2 = 0;
    }
    state(long long _d, int _u, bool _t1, bool _t2) {
        d = _d;
        u = _u;
        t1 = _t1;
        t2 = _t2;
    }
    bool operator < (const state &v) const {
        return d < v.d;
    }
    bool operator == (const state &v) const {
        return d == v.d;
    }
    bool operator > (const state &v) const {
        return d > v.d;
    }
};
long long d[NMAX + 5][2][2], len[2][NMAX + 5];
int start[2];
priority_queue<state, vector<state>, greater<state> > pq;
typedef pair<long long, int> pli;
priority_queue<pli, vector<pli>, greater<pli> > pq2;
void prepare(int t) {
    pq2.push({0, start[t]});
    len[t][start[t]] = 0;
    while(pq2.size()) {
        long long len_u = pq2.top().f;
        int u = pq2.top().s;
        pq2.pop();
        if(len_u != len[t][u])
            continue;
        for(pair<long long, int> &x : E[u]) {
            int v = x.s;
            long long uv = x.f;
            if(len[t][v] > len[t][u] + uv) {
                len[t][v] = len[t][u] + uv;
                pq2.push({len[t][v], v});
            }
        }
    }
}
void solve() {
    memset(d, 0x3f, sizeof d);
    d[U][0][0] = 0;
    pq.push(state(0, U, 0, 0));
    while(pq.size()) {
        int u = pq.top().u;
        long long du = pq.top().d;
        bool t1 = pq.top().t1;
        bool t2 = pq.top().t2;
        pq.pop();
        if(du != d[u][t1][t2])
            continue;
        for(pair<long long, int> &x : E[u]) {
            long long uv = x.f;
            int v = x.s;
            if(d[v][t1][0] > d[u][t1][t2] + uv) {
                d[v][t1][0] = d[u][t1][t2] + uv;
                pq.push(state(d[v][t1][0], v, t1, 0));
            }
            if(len[0][u] + uv + len[1][v] == len[0][T]) {
                if(t1 == 1 && t2 == 0)
                    continue;
                if(d[v][1][1] > d[u][t1][t2]) {
                    d[v][1][1] = d[u][t1][t2];
                    pq.push(state(d[v][1][1], v, 1, 1));
                }
            }
        }
    }
    res = min(res, min(d[V][1][1], d[V][1][0]));
    res = min(res, d[V][0][0]);
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen("BUS.INP", "r")) {
        freopen("BUS.INP", "r", stdin);
        freopen("BUS.OUT", "w", stdout);
    }
    cin >> N >> M >> S >> T >> U >> V;
    for(int i = 1; i <= M; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        E[u].push_back({w, v});
        E[v].push_back({w, u});
    }
    start[0] = S;
    start[1] = T;
    memset(len, 0x3f, sizeof len);
    for(int i = 0; i < 2; i++)
        prepare(i);
    res = 1e18;
    solve();
    swap(U, V);
    solve();
    cout << res;
}

Compilation message (stderr)

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

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