Submission #1052815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052815		fauz	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	520 ms	33256 KiB

commuter_pass

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

const int MAXN = 100001;

typedef pair<int, int> II;
typedef pair<long long, int> LLI;
typedef pair<long long, II> LLII;

int n, m, s, t, u, v;
long long ds[MAXN], dt[MAXN];
vector<II> g[MAXN];
set<LLI> q;

void dijk(int start, long long *d)
{
    for (int i = 1; i <= n; ++i)
        d[i] = LLONG_MAX;
    q.clear();
    d[start] = 0;
    q.insert(LLI(0, start));

    while (!q.empty())
    {
        int a = q.begin()->se;
        q.erase(q.begin());

        for (II x : g[a])
        {
            int b = x.fi, w = x.se;
            if (d[b] > d[a] + 1ll * w)
            {
                if (d[b] < LLONG_MAX)
                    q.erase(LLI(d[b], b));
                d[b] = d[a] + 1ll * w;
                q.insert(LLI(d[b], b));
            }
        }
    }
}

set<LLII> sLII;
long long d[4][MAXN];
long long get(int start, int stop)
{
    for (int j = 0; j < 4; ++j)
        for (int i = 1; i <= n; ++i)
            d[j][i] = LLONG_MAX;

    sLII.clear();
    d[0][start] = 0;
    sLII.insert(LLII(0, II(0, start)));
    while (!sLII.empty())
    {
        int a = sLII.begin()->se.se, type = sLII.begin()->se.fi;
        sLII.erase(sLII.begin());

        if (type < 3)
        {
            if (d[type + 1][a] > d[type][a] && (type == 2 || ds[a] + dt[a] == ds[t]))
            {
                if (d[type + 1][a] < LLONG_MAX)
                    sLII.erase(LLII(d[type + 1][a], II(type + 1, a)));
                d[type + 1][a] = d[type][a];
                sLII.insert(LLII(d[type + 1][a], II(type + 1, a)));
            }
        }

        for (II x : g[a])
        {
            int b = x.fi, w = x.se;

            if (d[type][b] > d[type][a] + 1ll * w && (type == 0 || (type == 1 && ds[b] + dt[b] == ds[t]) || (type == 2 && ds[a] + w + dt[b] == ds[t]) || type == 3))
            {
                if (d[type][b] < LLONG_MAX)
                    sLII.erase(LLII(d[type][b], II(type, b)));
                d[type][b] = d[type][a] + 1ll * ((type == 2) ? 0 : w);
                sLII.insert(LLII(d[type][b], II(type, b)));
            }
        }
    }

    long long ans = LLONG_MAX;
    for (int j = 0; j < 4; ++j)
        ans = min(ans, d[j][stop]);
    return ans;
}

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

    cin >> n >> m >> s >> t >> u >> v;
    for (int i = 1; i <= m; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back(II(b, c));
        g[b].push_back(II(a, c));
    }

    dijk(s, ds);
    dijk(t, dt);

    cout << min(get(u, v), get(v, u));
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int32_t 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("inp.txt", "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("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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