Submission #1264723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264723		tvgk	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	383 ms	8776 KiB

ho_t4

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define ll long long
#define ii pair<ll, ll>
#define fi first
#define se second
const long mxN = 1e5 + 7, inf = 2e9 + 7;

int n, m, u[mxN], v[mxN], c[mxN], sw[mxN];
ll mn[mxN][5];
ii trace[mxN][5];
bool use[5][mxN];
vector<ii> w[mxN][2];

void DFS(int stt, int en, int spe, int id, int tt)
{
    for (int i = 1; i <= n; i++)
    {
        mn[i][tt] = inf;
        trace[i][tt] = {0, 0};
    }

    priority_queue<ii, vector<ii>, greater<ii>> pq;
    pq.push({0, stt});
    mn[stt][tt] = 0;

    while (pq.size())
    {
        ii j = pq.top();
        pq.pop();

        if (j.fi != mn[j.se][tt])
            continue;

        for (ii i : w[j.se][id])
        {
            if (i.se != spe && mn[i.fi][tt] > j.fi + c[i.se])
            {
                mn[i.fi][tt] = j.fi + c[i.se];
                trace[i.fi][tt] = {j.se, i.se};
                pq.push({mn[i.fi][tt], i.fi});
            }
        }
    }

    while (en)
    {
        use[tt][trace[en][tt].se] = 1;
        en = trace[en][tt].fi;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(a".INP", "r", stdin);
    //freopen(a".OUT", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> u[i] >> v[i] >> c[i] >> sw[i];
        w[u[i]][0].push_back({v[i], i});
        w[v[i]][1].push_back({u[i], i});
    }
    DFS(1, n, 0, 0, 0);
    DFS(n, 1, 0, 0, 1);
    DFS(1, n, 0, 1, 2);
    DFS(n, 1, 0, 1, 3);

    ll ans = mn[n][0] + mn[1][1];
    for (int i = 1; i <= m; i++)
    {
        ll l, r;
        if (use[0][i])
        {
            w[v[i]][0].push_back({u[i], 0});
            DFS(1, n, i, 0, 4);
            w[v[i]][0].pop_back();
            l = mn[n][4];
        }
        else
            l = min(mn[n][0], mn[u[i]][3] + mn[v[i]][0] + c[i]);

        if (use[1][i])
        {
            w[u[i]][1].push_back({v[i], 0});
            DFS(n, 1, i, 0, 4);
            w[u[i]][1].pop_back();
            r = mn[1][4];
        }
        else
            r = min(mn[1][1], mn[u[i]][2] + mn[v[i]][1] + c[i]);
            
        ans = min(l + r + sw[i], ans);
    }

    if (ans >= inf)
        cout << -1;
    else
        cout << ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 63 / 63