Submission #1161737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161737		12345678	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	564 ms	4936 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=205, mx=5e4+5;

ll n, m, u[mx], v[mx], s[mx], rs[mx], c[mx], f[mx],vs[nx], cur, res=1e18;
vector<vector<pair<ll, ll>>> d(nx), rv(nx);
vector<ll> st(nx), ed(nx), rst(nx), red(nx), tmp1(nx), tmp2(nx);
vector<pair<ll, ll>> b(nx), rb(nx), h(nx);

void dijkstra(ll rt, vector<ll> &mn, vector<vector<pair<ll, ll>>> &g, ll ban, vector<pair<ll, ll>> &bk)
{
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    for (int i=1; i<=n ;i++) mn[i]=1e18, vs[i]=0;
    mn[rt]=0;
    bk[rt]={-1, -1};
    pq.push({0, rt});
    while (!pq.empty())
    {
        auto [cw, u]=pq.top();
        pq.pop();
        if (vs[u]) continue;
        vs[u]=1;
        for (auto [v, idx]:g[u])
        {
            if (idx==ban) continue;
            if (mn[v]>cw+c[idx]) bk[v]={u, idx}, mn[v]=cw+c[idx], pq.push({mn[v], v});
        }
    }
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=m; i++) cin>>u[i]>>v[i]>>c[i]>>f[i], d[u[i]].push_back({v[i], i}), rv[v[i]].push_back({u[i], i});
    dijkstra(1, st, d, -1, b);
    dijkstra(n, ed, d, -1, rb);
    dijkstra(1, rst, rv, -1, h);
    dijkstra(n, red, rv, -1, h);
    if (st[n]!=1e18)
    {
        cur=n;
        while (b[cur].second!=-1) s[b[cur].second]=1, cur=b[cur].first;
    }
    if (ed[1]!=1e18)
    {
        cur=1;
        while (rb[cur].second!=-1) rs[rb[cur].second]=1, cur=rb[cur].first;
    }
    res=min(res, st[n]+ed[1]);
    for (int i=1; i<=m; i++)
    {
        if (s[i]||rs[i])
        {
            c[m+1]=c[i];
            d[v[i]].push_back({u[i], m+1});
            dijkstra(1, tmp1, d, i, h);
            dijkstra(n, tmp2, d, i, h);
            d[v[i]].pop_back();
            res=min(res, tmp1[n]+tmp2[1]+f[i]);
        }
        else
        {
            res=min(res, min(st[n], st[v[i]]+c[i]+red[u[i]])+min(ed[1], ed[v[i]]+c[i]+rst[u[i]])+f[i]);
        }
        //cout<<"res "<<i<<' '<<res<<'\n';
    }
    if (res==1e18) cout<<-1;
    else cout<<res;
}

/*
2 2
1 2 3 3
1 2 3 3

4 5
1 2 1 1
3 2 1 1
3 4 1 1
4 2 1 1
3 1 1 1
*/

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