oj.uz

Submission #444363

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

const long long INF = 1'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 56 ms 708 KB Output is correct
2 Correct 10 ms 652 KB Output is correct
3 Correct 86 ms 704 KB Output is correct
4 Correct 83 ms 700 KB Output is correct
5 Correct 5 ms 588 KB Output is correct
6 Correct 12 ms 716 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 69 ms 588 KB Output is correct
11 Correct 90 ms 696 KB Output is correct
12 Correct 85 ms 588 KB Output is correct
13 Incorrect 33 ms 700 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 3812 KB Output is correct
2 Correct 717 ms 3688 KB Output is correct
3 Correct 704 ms 3780 KB Output is correct
4 Correct 79 ms 716 KB Output is correct
5 Correct 52 ms 684 KB Output is correct
6 Correct 11 ms 676 KB Output is correct
7 Correct 13 ms 660 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Incorrect 362 ms 3780 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 588 KB Output is correct
2 Correct 18 ms 664 KB Output is correct
3 Correct 680 ms 3080 KB Output is correct
4 Correct 14 ms 588 KB Output is correct
5 Correct 882 ms 3780 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Incorrect 510 ms 3764 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 708 KB Output is correct
2 Correct 10 ms 652 KB Output is correct
3 Correct 86 ms 704 KB Output is correct
4 Correct 83 ms 700 KB Output is correct
5 Correct 5 ms 588 KB Output is correct
6 Correct 12 ms 716 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 69 ms 588 KB Output is correct
11 Correct 90 ms 696 KB Output is correct
12 Correct 85 ms 588 KB Output is correct
13 Incorrect 33 ms 700 KB Output isn't correct
14 Halted 0 ms 0 KB -