oj.uz

Submission #444362

# Submission time Handle Problem Language Result Execution time Memory
444362 2021-07-13T18:29:59 Z blue Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 860 ms 5188 KB 
#include <iostream>
#include <vector>
#include <set>
using namespace std;

const long long INF = 1'000'000'000'000'000LL;

const int maxN = 200;

struct edge
{
    int i;
    int v;
    long long fare;
    long long modify_cost;
};

bool operator < (edge E, edge F)
{
    return E.i < F.i;
};

multiset<edge> E[1+maxN];

vector< vector<long long> > dist(1+maxN, vector<long long>(1+maxN, INF));

vector<long long> dist1(1+maxN, INF);
vector<int> prevNode(1+maxN, -1);
vector<edge> prevEdge(1+maxN);

struct pos
{
    int i;
};

bool operator < (pos X, pos Y)
{
    if(dist1[X.i] == dist1[Y.i]) return X.i < Y.i;
    return dist1[X.i] < dist1[Y.i];
}



vector<long long> distN(1+maxN, INF);
vector<int> prevNodeN(1+maxN, -1);
vector<edge> prevEdgeN(1+maxN);

struct posN
{
    int i;
};

bool operator < (posN X, posN Y)
{
    if(distN[X.i] == distN[Y.i]) return X.i < Y.i;
    return distN[X.i] < distN[Y.i];
}






int main()
{
    int N, M;
    cin >> N >> M;

    for(int i = 1; i <= N; i++) dist[i][i] = 0;

    for(int e = 1; e <= M; e++)
    {
        int U, V, C, D;
        cin >> U >> V >> C >> D;

        E[U].insert(edge{e, V, C, D});

        dist[U][V] = min(dist[U][V], (long long)C);
    }

    long long ans = INF;

    //Part 1: Don't reverse anything

    for(int k = 1; k <= N; k++)
        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= N; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    ans = min(ans, dist[1][N] + dist[N][1]);



    //Part 2: Compute dijkstra tree
    dist1[1] = 0;
    set<pos> tbv;
    for(int i = 1; i <= N; i++) tbv.insert(pos{i});

    while(!tbv.empty())
    {
        int u = tbv.begin()->i;
        tbv.erase(tbv.begin());

        for(edge e:E[u])
        {
            int v = e.v;
            long long w = e.fare;

            if(dist1[u] + w < dist1[v])
            {
                tbv.erase(pos{v});
                dist1[v] = dist1[u] + w;
                prevNode[v] = u;
                prevEdge[v] = e;
                tbv.insert(pos{v});
            }
        }
    }


    // cerr << "ans = " << ans << '\n';





    distN[N] = 0;
    set<posN> tbvN;
    for(int i = 1; i <= N; i++) tbvN.insert(posN{i});

    while(!tbvN.empty())
    {
        int u = tbvN.begin()->i;
        tbvN.erase(tbvN.begin());

        for(edge e:E[u])
        {
            int v = e.v;
            long long w = e.fare;

            if(distN[u] + w < distN[v])
            {
                tbvN.erase(posN{v});
                distN[v] = distN[u] + w;
                prevNodeN[v] = u;
                prevEdgeN[v] = e;
                tbvN.insert(posN{v});
            }
        }
    }










    // cerr << "check\n";

    // cerr << prevNode[N] << '\n';


    for(int u = 1; u <= N; u++)
    {
        // cerr << "\n\n\n";
        // cerr << "u = " << u << '\n';
        multiset<edge> E1 = E[u];
        for(edge e: E1)
        {
            // cerr << "e = " << e.i << ' ' << e.v << ' ' << e.fare << ' ' << e.modify_cost << '\n';
            // cerr << "v = " << e.v << '\n';
            int v = e.v;
            bool flag1 = 0, flag2 = 0;

            if(prevEdge[v].i != e.i)
            {
                ans = min(ans, dist[1][N] + dist[N][v] + e.fare + e.modify_cost + dist[u][1]);
                flag1 = 1;
            }

            if(prevEdgeN[v].i != e.i)
            {
                ans = min(ans, dist[1][v] + e.fare + e.modify_cost + dist[u][N] + dist[N][1]);
                flag2 = 1;
            }


            if(!flag1 || !flag2)
            {
                E[u].erase(E[u].find(e));
                E[v].insert(edge{M+1, u, e.fare, e.modify_cost});




                dist1[1] = 0;
                for(int i = 2; i <= N; i++) dist1[i] = INF;

                for(int i = 1; i <= N; i++) tbv.insert(pos{i});

                while(!tbv.empty())
                {
                    int u = tbv.begin()->i;
                    tbv.erase(tbv.begin());

                    for(edge e:E[u])
                    {
                        int v = e.v;
                        long long w = e.fare;

                        if(dist1[u] + w < dist1[v])
                        {
                            tbv.erase(pos{v});
                            dist1[v] = dist1[u] + w;
                            tbv.insert(pos{v});
                        }
                    }
                }












                distN[N] = 0;
                for(int i = 1; i < N; i++) distN[i] = INF;

                for(int i = 1; i <= N; i++) tbvN.insert(posN{i});

                while(!tbvN.empty())
                {
                    int u = tbvN.begin()->i;
                    tbvN.erase(tbvN.begin());

                    for(edge e:E[u])
                    {
                        int v = e.v;
                        long long w = e.fare;

                        if(distN[u] + w < distN[v])
                        {
                            tbvN.erase(posN{v});
                            distN[v] = distN[u] + w;
                            tbvN.insert(posN{v});
                        }
                    }
                }







                E[v].erase(E[v].find(edge{M+1, u, e.fare, e.modify_cost}));
                E[u].insert(e);



                ans = min(ans, dist1[N] + distN[1] + e.modify_cost);
            }

            // cerr << "e = " << e.i << ", ans = " << ans << '\n';
        }
    }

    if(ans >= INF) ans = -1;
    cout << ans << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 716 KB Output is correct
2 Correct 11 ms 656 KB Output is correct
3 Correct 76 ms 720 KB Output is correct
4 Correct 82 ms 724 KB Output is correct
5 Correct 5 ms 716 KB Output is correct
6 Correct 11 ms 660 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 72 ms 716 KB Output is correct
11 Correct 91 ms 720 KB Output is correct
12 Correct 87 ms 716 KB Output is correct
13 Incorrect 32 ms 716 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 686 ms 4788 KB Output is correct
2 Correct 726 ms 4736 KB Output is correct
3 Correct 697 ms 5188 KB Output is correct
4 Correct 79 ms 716 KB Output is correct
5 Correct 51 ms 720 KB Output is correct
6 Correct 11 ms 680 KB Output is correct
7 Correct 13 ms 668 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Incorrect 350 ms 4372 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 716 KB Output is correct
2 Correct 18 ms 652 KB Output is correct
3 Correct 684 ms 3676 KB Output is correct
4 Correct 14 ms 588 KB Output is correct
5 Correct 860 ms 4488 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Incorrect 504 ms 4504 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 716 KB Output is correct
2 Correct 11 ms 656 KB Output is correct
3 Correct 76 ms 720 KB Output is correct
4 Correct 82 ms 724 KB Output is correct
5 Correct 5 ms 716 KB Output is correct
6 Correct 11 ms 660 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 72 ms 716 KB Output is correct
11 Correct 91 ms 720 KB Output is correct
12 Correct 87 ms 716 KB Output is correct
13 Incorrect 32 ms 716 KB Output isn't correct
14 Halted 0 ms 0 KB -