Submission #1227366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227366		_noob	Commuter Pass (JOI18_commuter_pass)	C++20	16 / 100	166 ms	19364 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
#define fo(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define ford(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define rep(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define double long double
#define iii pair <int, pair <int, int>>
#define sz(a) (int)a.size()
#define fi first
#define sc second
#define all(a) a.begin(), a.end()
#define ii pair <int, int> 
#define int long long 
template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } else return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } else return false;
    }
template<class T>
    T Abs(const T &x) {
        return (x < 0 ? -x : x);
    }


const int N = 1e5 + 9;
const int MOD = 1e9 + 7;
const int INF = 1e18;

int n, m;
int s, t, U, V;
vector <ii> a[N];
int d_s[N], d_t[N];

void dijsktra ()
{
    memset (d_s, 0x3f, sizeof(d_s));
    priority_queue<ii, vector <ii>, greater <ii>> pq;
    d_s[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        int u = pq.top().second;
        int du = pq.top().first;
        pq.pop();
        if (du != d_s[u]) continue;
        for (auto V : a[u]) {
            int w = V.second;
            int v = V.first;
            if (d_s[v] > d_s[u] + w) {
                d_s[v] = d_s[u] + w;
                pq.push({d_s[v], v});
            }
        }
    }
}

void dijsktra2 ()
{
    memset(d_t, 0x3f, sizeof(d_t))   ;
    priority_queue<ii, vector <ii>, greater <ii>> pq;
    d_t[t] = 0;
    pq.push({0, t});
    while (!pq.empty()) {
        int u = pq.top().second;
        int du = pq.top().first;
        pq.pop();
        if (du != d_t[u]) continue;
        for (auto V : a[u]) {
            int w = V.second;
            int v = V.first;
            if (d_t[v] > d_t[u] + w) {
                d_t[v] = d_t[u] + w;
                pq.push({d_t[v], v});
            }
        }
    }
}

int d[N];
bool can (int u, int v, int w)
{
    return (d_s[u] + d_t[v] + w == d_s[t]);
}
void dijsktra3()
{
    memset (d, 0x3f, sizeof(d));
    d[U] = 0;
    priority_queue <ii, vector <ii>, greater <ii>> pq;
    pq.push({0, U});
    while (!pq.empty()) {
        int u = pq.top().second;
        int du = pq.top().first;
        pq.pop();
        if (du != d[u]) continue;
        for (auto V : a[u]) {
            int v = V.first;
            int w = V.second;
            w = (can(u, v, w) ? 0 : w);
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
        }
    }
}
int d_1[N];
void dijsktra4()
{
    memset (d_1, 0x3f, sizeof(d));
    d_1[V] = 0;
    priority_queue <ii, vector <ii>, greater <ii>> pq;
    pq.push({0, V});
    while (!pq.empty()) {
        int u = pq.top().second;
        int du = pq.top().first;
        pq.pop();
        if (du != d_1[u]) continue;
        for (auto V : a[u]) {
            int v = V.first;
            int w = V.second;
            if (d_1[v] > d_1[u] + w) {
                d_1[v] = d_1[u] + w;
                pq.push({d_1[v], v});
            }
        }
    }
}
signed main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    cin >> s >> t;
    cin >> U >> V;
    fo(i, 1, m) {
        int u, v, w;
        cin >> u >> v >> w;
        a[u].push_back({v, w});
        a[v].push_back({u, w});
    }
    dijsktra();
    dijsktra2();
    dijsktra3();
    dijsktra4();
    cout << min(d[V], d_1[U]);
}
/**

**/

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