Submission #844256

#	Time	Username	Problem	Language	Result	Execution time	Memory
844256		hct_2so1	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	265 ms	16968 KiB

commuter_pass

#include <bits/stdc++.h>

#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define uni(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define F first
#define S second
#define pii(x, y) make_pair(x, y)
#define __builtin_popcount __builtin_popcountll
#define __builtin_ctz __builtin_ctzll
#define __builtin_clz __builtin_clzll
#define lg(x) (63 - __builtin_clz(x))

template <class X, class Y>
    bool minimize(X &x, const Y &y)
    {
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y)
    {
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }

using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int M = 6e5;
const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const ll oo = 2e18;
const double eps = 1e-1;
const long double pi = 2*acos(0.0);

int n, m, s, t, U, V;
bool vs[N];
ll dp[4][N], f[N][2];
vector<pair<int, int>> ar[N];

void Input(void)
{
    cin >> n >> m >> s >> t >> U >> V;
    for (int i = 1; i <= m; i ++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        ar[u].push_back(pii(v, w));
        ar[v].push_back(pii(u, w));
    }
}

void dijkstra(int idx, int source)
{
    priority_queue<pair<ll, int>> st;
    dp[idx][source] = 0;
    st.push(pii(0, source));
    while (sz(st))
    {
        auto [w, u] = st.top(); st.pop();
        w = -w;
        if (dp[idx][u] < w) continue;
        for (auto [v, wi] : ar[u])
            if (minimize(dp[idx][v], w + wi)) st.push(pii(- dp[idx][v], v));
    }
}

ll ans = oo;

void bfs(int u)
{
    f[u][0] = dp[2][u];
    f[u][1] = dp[3][u];
    queue<int> st;
    st.push(u);
    vs[u] = 1;
    while (sz(st))
    {
        int source = st.front(); st.pop();
        minimize(ans, f[source][1] + dp[2][source]);
        minimize(ans, f[source][0] + dp[3][source]);
        for (auto [sink, w] : ar[source])
            if (dp[0][source] + w + dp[1][sink] == dp[0][t])
            {
                minimize(f[sink][0], min(f[source][0], dp[2][sink]));
                minimize(f[sink][1], min(f[source][1], dp[3][sink]));
                if (!vs[sink]) st.push(sink);
                vs[sink] = 1;
            }
    }
}

void solve(void)
{
    memset(dp, 0x3f, sizeof dp);
    dijkstra(0, s);
    dijkstra(1, t);
    dijkstra(2, U);
    dijkstra(3, V);
    memset(f, 0x3f, sizeof f);
    bfs(s);
    cout << min(ans, dp[2][V]);
}

int main()
{
    std::ios_base::sync_with_stdio(0); cin.tie(0);
    int test = 1;
    //cin >> test;
    while (test --)
    {
        Input();
        solve();
    }
    return 0;
}

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