Submission #1184251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184251		jerzyk	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	17 ms	3472 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 100'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 207;
const int K = 50'007;
pair<pair<int, int>, pair<int, int>> e[K];

vector<pair<int, pair<int, int>>> edf[N];
vector<pair<int, pair<int, int>>> edf2[N];

vector<pair<int, int>> ed[N], ed2[N];
vector<int> pth; int czy[K];
ll dis[2 * N]; int vis[2 * N], sk[N];
int tab[N];

ll d1[N], d2[N];

void DijkstraF(int n)
{
    for(int i = 0; i <= n; ++i) {dis[i] = I; vis[i] = 0;}
    dis[1] = 0;
    while(true)
    {
        int v = 0;
        for(int i = 1; i <= n; ++i)
            if(!vis[i] && dis[i] < dis[v]) v = i;
        if(v == 0) break;
        vis[v] = 1;
        for(int i = 0; i < (int)edf[v].size(); ++i)
        {
            ll o = dis[v] + (ll)edf[v][i].nd.st;
            if(o < dis[edf[v][i].st])
            {
                dis[edf[v][i].st] = o; sk[edf[v][i].st] = edf[v][i].nd.nd;
            }
        }
    }
    int v = n;
    if(dis[n] == I) return;
    while(v != 1)
    {
        pth.pb(sk[v]);
        czy[sk[v]] = 1;
        if(e[sk[v]].st.st != v) v = e[sk[v]].st.st;
        else v = e[sk[v]].st.nd;
    }
}

void Dijkstra(int n, int s)
{
    for(int i = 0; i <= 2 * n; ++i) {dis[i] = I; vis[i] = 0;}
    dis[s] = 0;
    while(true)
    {
        int v = 0, u;
        for(int i = 1; i <= 2 * n; ++i)
            if(!vis[i] && dis[i] < dis[v]) v = i;
        if(v == 0) break;
        //cerr << v << " " << ed[v].size() << "  " << ed2[v].size() << "\n";
        vis[v] = 1;
        u = v;
        if(v > n) v -= n;
        for(int i = 0; i < (int)ed[v].size(); ++i)
        {
            int ne = ed[v][i].st + (u - v);
            ll d = dis[v] + ed[v][i].nd;
            if(d < dis[ne])
                dis[ne] = d;
        }
        if(u > n) continue;
        for(int i = 0; i < (int)ed2[v].size(); ++i)
        {
            int ne = ed2[v][i].st + n;
            ll d = dis[v] + ed2[v][i].nd;
            if(d < dis[ne])
                dis[ne] = d;
        }
    }
}

ll Licz(int n, int m)
{
    ll ans = I;
    for(int i = 1; i <= n; ++i)
        {ed[i].clear(); ed2[i].clear();}
    for(int i = 1; i <= m; ++i)
        ed[e[i].st.st].pb(make_pair(e[i].st.nd, e[i].nd.st));
    Dijkstra(n, 1);
    for(int i = 1; i <= n; ++i) d1[i] = dis[i];
    Dijkstra(n, n);
    for(int i = 1; i <= n; ++i) d1[i] += dis[i];

    for(int i = 1; i <= n; ++i)
        ed[i].clear();
    for(int i = 1; i <= m; ++i)
        ed[e[i].st.nd].pb(make_pair(e[i].st.st, e[i].nd.st));
    Dijkstra(n, 1);
    for(int i = 1; i <= n; ++i) d2[i] = dis[i];
    Dijkstra(n, n);
    for(int i = 1; i <= n; ++i) d2[i] += dis[i];

    for(int i = 1; i <= m; ++i)
        ans = min(ans, d1[e[i].st.nd] + d2[e[i].st.st] + (ll)e[i].nd.st + (ll)e[i].nd.nd);
    return ans;
}

void Solve()
{
    int n, m, a, b, c1, c2;
    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        cin >> a >> b >> c1 >> c2;
        edf[a].pb(make_pair(b, make_pair(c1, i)));
        e[i] = make_pair(make_pair(a, b), make_pair(c1, c2));
    }
    DijkstraF(n);
    if(dis[n] == I)
    {
        for(int i = 1; i <= n; ++i)
            edf[i].clear();
        for(int i = 1; i <= m; ++i)
        {
            a = n - e[i].st.st + 1; b = n - e[i].st.nd + 1; c1 = e[i].nd.st; c2 = e[i].nd.nd;
            edf[a].pb(make_pair(b, make_pair(c1, i)));
            e[i] = make_pair(make_pair(a, b), make_pair(c1, c2));
        }
        DijkstraF(n);
    }
    ll ans = I, cur = dis[n];
    for(int i = 1; i <= m; ++i)
    {
        ed[e[i].st.st].pb(make_pair(e[i].st.nd, e[i].nd.st));
        if(czy[i]) continue;
        ed2[e[i].st.nd].pb(make_pair(e[i].st.st, e[i].nd.st + e[i].nd.nd));
    }
    Dijkstra(n, n);
    cur += min(dis[1], dis[1 + n]);
    ans = cur;

    for(int l = 0; l < (int)pth.size(); ++l)
    {
        for(int i = 1; i <= n; ++i)
        {ed[i].clear(); ed2[i].clear();}
        for(int i = 1; i <= m; ++i)
        {
            if(i == pth[l])
                ed2[e[i].st.nd].pb(make_pair(e[i].st.st, e[i].nd.st + e[i].nd.nd));
            else
                ed[e[i].st.st].pb(make_pair(e[i].st.nd, e[i].nd.st));
        }
        Dijkstra(n, 1);
        cur = min(dis[n], dis[n + n]);
        Dijkstra(n, n);
        cur += min(dis[1], dis[1 + n]);
        //cout << "C: " << l << " " << pth[l] << " " << cur << " " << ans << "\n";
        ans = min(ans, cur);
    }
    ans = min(ans, Licz(n, m));
    if(ans < I)
        cout << ans << "\n";
    else
        cout << -1 << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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