Submission #1154907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154907		trinm01	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	368 ms	96524 KiB

commuter_pass

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

#define int long long
#define ll long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, r, l) for (int i = (r); i >= (l); i--)
#define fi first
#define se second
#define pii pair<int, int>

const ll mod = 1e9 + 7;
const ll MAXN = 1e6 + 5;
const ll oo = 1e18;

int n, m, s1, t1, s2, t2, f1[MAXN], f2[MAXN], chk[MAXN], f[MAXN][4];
vector<pii> adj[MAXN], adj1[MAXN];
struct note
{
    int u, v, c;
} canh[MAXN];

void dijkstra1()
{
    priority_queue<pii, vector<pii>, greater<pii>> q;
    FOR(i, 1, n)
    {
        f1[i] = oo;
    }
    f1[s1] = 0;
    q.push({0, s1});
    while (q.size())
    {
        auto [c, u] = q.top();
        q.pop();
        if (c > f1[u])
            continue;
        for (auto &[v, w] : adj[u])
        {
            if (f1[v] > f1[u] + w)
            {
                f1[v] = f1[u] + w;
                q.push({f1[v], v});
            }
        }
    }
}

void dijkstra2()
{
    priority_queue<pii, vector<pii>, greater<pii>> q;
    FOR(i, 1, n)
    {
        f2[i] = oo;
    }
    f2[t1] = 0;
    q.push({0, t1});
    while (q.size())
    {
        auto [c, u] = q.top();
        q.pop();
        if (c > f2[u])
            continue;
        for (auto &[v, w] : adj[u])
        {
            if (f2[v] > f2[u] + w)
            {
                f2[v] = f2[u] + w;
                q.push({f2[v], v});
            }
        }
    }
}

void dijkstra()
{
    priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> q;
    FOR(i, 1, n)
    {
        FOR(j, 0, 2)
        {
            f[i][j] = oo;
        }
    }
    FOR(j, 0, 2)
    {
        f[s2][j] = 0;
        q.push({0, {s2, j}});
    }
    while (q.size())
    {
        int c = q.top().fi;
        auto [u, tt] = q.top().se;
        q.pop();
        if (c > f[u][tt])
        {
            continue;
        }
        for (auto &[v, w] : adj1[u])
        {
            FOR(j, 0, 2)
            {
                if (j == 1)
                    continue;
                if (f[v][j] > f[u][tt] + w)
                {
                    f[v][j] = f[u][tt] + w;
                    q.push({f[v][j], {v, j}});
                }
            }
            if (w == 0)
            {
                if (tt == 0)
                {
                    if (f[v][1] > f[u][0])
                    {
                        f[v][1] = f[u][0];
                        q.push({f[v][1], {v, 1}});
                    }
                }
                else if (tt == 1)
                {
                    if (f[v][1] > f[u][1])
                    {
                        f[v][1] = f[u][1];
                        q.push({f[v][1], {v, 1}});
                    }
                }
                else
                {
                    if (f[v][2] > f[u][2] + w)
                    {
                        f[v][2] = f[u][2] + w;
                        q.push({f[v][2], {v, 2}});
                    }
                }
            }
            else
            {
                if (tt == 0)
                {
                    if (f[v][0] > f[u][0] + w)
                    {
                        f[v][0] = f[u][0] + w;
                        q.push({f[v][0], {v, 0}});
                    }
                }
                else if (tt == 1)
                {
                    if (f[v][2] > f[u][1] + w)
                    {
                        f[v][2] = f[u][1] + w;
                        q.push({f[v][2], {v, 2}});
                    }
                }
                else
                {
                    if (f[v][2] > f[u][2] + w)
                    {
                        f[v][2] = f[u][2] + w;
                        q.push({f[v][2], {v, 2}});
                    }
                }
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    if (fopen("DAYCON.inp", "r"))
    {
        freopen("DAYCON.inp", "r", stdin);
        freopen("DAYCON.out", "w", stdout);
    }

    cin >> n >> m >> s1 >> t1 >> s2 >> t2;

    FOR(i, 1, m)
    {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
        adj1[u].push_back({v, c});
        adj1[v].push_back({u, c});
        canh[i] = {u, v, c};
        canh[i + m] = {v, u, c};
    }

    dijkstra1();
    dijkstra2();

    m *= 2;
    FOR(i, 1, m)
    {
        auto [u, v, c] = canh[i];
        if (f1[u] + c + f2[v] == f1[t1])
        {
            adj1[u].push_back({v, 0});
        }
    }

    // cout << chk[4] << ' ';

    dijkstra();

    int ans = oo;
    FOR(i, 0, 2)
    {
        ans = min(ans, f[t2][i]);
    }

    FOR(i, 1, n)
    {
        adj1[i].clear();
    }

    FOR(i, 1, m)
    {
        auto [u, v, c] = canh[i];
        // adj1[v].push_back({u, c});
        adj1[u].push_back({v, c});
    }

    FOR(i, 1, m)
    {
        auto [u, v, c] = canh[i];
        if (f2[u] + c + f1[v] == f1[t1])
        {
            adj1[u].push_back({v, 0});
        }
    }

    dijkstra();

    FOR(i, 0, 2)
    {
        ans = min(ans, f[t2][i]);
    }

    cout << ans;

    return 0;
}

Compilation message (stderr)

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

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