Submission #1155195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155195		cpismylifeOwO	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	257 ms	3604 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

const long long inf = 1e18 + 1;
const long long mod = 1e9 + 7;
const int MaxN = 2e2 + 5;
const int MaxM = 5e4 + 5;

struct Edge
{
    int u, v;
    long long c, d;
};

int n, m;
Edge edges[MaxM];
vector<int> graph[MaxN];
vector<int> revgraph[MaxN];

void Inp()
{
    cin >> n >> m;
    for (int x = 1; x <= m; x++)
    {
        cin >> edges[x].u >> edges[x].v >> edges[x].c >> edges[x].d;
        graph[edges[x].u].push_back(x);
        revgraph[edges[x].v].push_back(x);
    }
}

long long Dis[2][MaxN][MaxN];
bool visited[MaxN];
long long curDis[MaxN];

void Dijkstra(int id, int s, int k)
{
    for (int x = 1; x <= n; x++)
    {
        visited[x] = false;
        Dis[id][x][k] = inf;
        curDis[x] = inf;
    }
    visited[k] = true;
    Dis[id][s][k] = 0;
    curDis[s] = 0;
    while (true)
    {
        pair<long long, int> p = make_pair(inf, 0);
        for (int x = 1; x <= n; x++)
        {
            if (!visited[x] && curDis[x] < inf)
            {
                p = min(p, make_pair(curDis[x], x));
            }
        }
        if (p.second == 0)
        {
            break;
        }
        int u = p.second;
        visited[u] = true;
        Dis[id][u][k] = curDis[u];
        for (int id : graph[u])
        {
            int v = edges[id].v;
            long long w = edges[id].c;
            if (!visited[v])
            {
                curDis[v] = min(curDis[v], curDis[u] + w);
            }
        }
        curDis[u] = inf;
    }
}

long long revDis[2][MaxN][MaxN];

void RevDijkstra(int id, int s, int k)
{
    for (int x = 1; x <= n; x++)
    {
        visited[x] = false;
        revDis[id][x][k] = inf;
        curDis[x] = inf;
    }
    visited[k] = true;
    revDis[id][s][k] = 0;
    curDis[s] = 0;
    while (true)
    {
        pair<long long, int> p = make_pair(inf, 0);
        for (int x = 1; x <= n; x++)
        {
            if (!visited[x] && curDis[x] < inf)
            {
                p = min(p, make_pair(curDis[x], x));
            }
        }
        if (p.second == 0)
        {
            break;
        }
        int u = p.second;
        visited[u] = true;
        revDis[id][u][k] = curDis[u];
        for (int id : revgraph[u])
        {
            int v = edges[id].u;
            long long w = edges[id].c;
            if (!visited[v])
            {
                curDis[v] = min(curDis[v], curDis[u] + w);
            }
        }
        curDis[u] = inf;
    }
}

long long best[2][MaxN];
long long revbest[2][MaxN];
long long secbest[2][MaxN];
long long revsecbest[2][MaxN];
int posbest[2][MaxN];
int revposbest[2][MaxN];

void Exc()
{
    Dijkstra(0, 1, 0);
    Dijkstra(1, n, 0);
    for (int x = 1; x <= n; x++)
    {
        Dis[0][x][1] = inf;
        Dis[1][x][n] = inf;
    }
    for (int x = 2; x <= n; x++)
    {
        Dijkstra(0, 1, x);
    }
    for (int x = 1; x < n; x++)
    {
        Dijkstra(1, n, x);
    }
    RevDijkstra(0, 1, 0);
    RevDijkstra(1, n, 0);
    for (int x = 1; x <= n; x++)
    {
        revDis[1][x][n] = inf;
        revDis[0][x][1] = inf;
    }
    for (int x = 2; x <= n; x++)
    {
        RevDijkstra(0, 1, x);
    }
    for (int x = 1; x < n; x++)
    {
        RevDijkstra(1, n, x);
    }
    long long res = min(Dis[0][n][0] + Dis[1][1][0], inf);
    for (int id = 0; id < 2; id++)
    {
        for (int x = 1; x <= n; x++)
        {
            best[id][x] = secbest[id][x] = inf;
            posbest[id][x] = 0;
            if (id == 0 && x == 1)
            {
                best[id][x] = 0;
                continue;
            }
            if (id == 1 && x == n)
            {
                best[id][x] = 0;
                continue;
            }
            for (int y : revgraph[x])
            {
                int u = edges[y].u;
                long long w = edges[y].c;
                if (best[id][x] > Dis[id][u][x] + w)
                {
                    secbest[id][x] = best[id][x];
                    best[id][x] = Dis[id][u][x] + w;
                    posbest[id][x] = y;
                }
                else if (secbest[id][x] > Dis[id][u][x] + w)
                {
                    secbest[id][x] = Dis[id][u][x] + w;
                }
            }
        }
    }
    for (int id = 1; id < 2; id++)
    {
        for (int x = 1; x <= n; x++)
        {
            revbest[id][x] = revsecbest[id][x] = inf;
            revposbest[id][x] = 0;
            if (id == 0 && x == 1)
            {
                revbest[id][x] = 0;
                continue;
            }
            if (id == 1 && x == n)
            {
                revbest[id][x] = 0;
                continue;
            }
            for (int y : graph[x])
            {
                int u = edges[y].v;
                long long w = edges[y].c;
                if (revbest[id][x] > revDis[id][u][x] + w)
                {
                    revsecbest[id][x] = revbest[id][x];
                    revbest[id][x] = revDis[id][u][x] + w;
                    revposbest[id][x] = y;
                }
                else if (revsecbest[id][x] > revDis[id][u][x] + w)
                {
                    revsecbest[id][x] = revDis[id][u][x] + w;
                }
            }
        }
    }
    for (int x = 1; x <= m; x++)
    {
        int u = edges[x].u, v = edges[x].v;
        long long w = edges[x].c;
        long long cur = edges[x].d;
        long long p1 = w, p11 = revDis[1][v][0];
        if (posbest[0][v] == x)
        {
            p1 += secbest[0][v];
            p11 += secbest[0][v];
        }
        else
        {
            p1 += best[0][v];
            p11 += best[0][v];
        }
        if (revposbest[1][u] == x)
        {
            p1 += secbest[1][u];
        }
        else
        {
            p1 += best[1][u];
        }
        cur += min(p1, min(Dis[0][n][v], p11));
        p1 = w;
        p11 = revDis[0][v][0];
        if (posbest[1][v] == x)
        {
            p1 += secbest[1][v];
            p11 += secbest[1][v];
        }
        else
        {
            p1 += best[1][v];
            p11 += best[1][v];
        }
        if (revposbest[0][u] == x)
        {
            p1 += secbest[0][u];
        }
        else
        {
            p1 += best[0][u];
        }
        cur += min(p1, min(Dis[1][1][v], p11));
        res = min(res, cur);
    }
    if (res >= inf)
    {
        cout << -1;
    }
    else
    {
        cout << res;
    }
}

int main()
{
    //freopen("C.INP", "r", stdin);
    //freopen("C.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}

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