Submission #444363

#	Time	Username	Problem	Language	Result	Execution time	Memory
444363		blue	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	882 ms	3812 KiB

ho_t4

#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
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63