Submission #236600

#	Time	Username	Problem	Language	Result	Execution time	Memory
236600		Charis02	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	287 ms	10116 KiB

ho_t4

#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 204
#define M 50005
#define INF 1e15

using namespace std;

struct edge{
    ll to;
    ll cost;
    ll reverse_cost;
    ll id;
    ll from;

    bool operator <(const edge &a)const
    {
        return id < a.id;
    }
    bool operator ==(const edge &a)
    {
        return a.id == id;
    }
};

ll n,m;
vector < edge > graph[N],inverse[N];
ll dist[N][N][4];
ll from_where[N][N][4];
bool is_interesting[M];
bool vis[N];
vector < edge > edges;
edge antestram;

void dijkstra(ll source,vector < edge > g[N],ll inv)
{
    rep(i,0,n+1)
    {
        vis[i]=false;
        dist[source][i][inv] = INF;
    }

    dist[source][source][inv] = 0;

    rep(iterations,0,n)
    {
        ll cur = 0;

        rep(i,1,n+1)
        {
            if(!vis[i] && dist[source][i][inv] < dist[source][cur][inv])
                cur=i;
        }

        vis[cur] = true;

        for(auto ed : g[cur])
        {
            ll v = ed.to;
            ll cc = ed.cost;
            ll ide = ed.id;

            if(ide == antestram.id)
            {
                continue;
            }

            if(dist[source][v][inv] > dist[source][cur][inv] + cc)
            {
                from_where[source][v][inv] = ide;
                dist[source][v][inv] = dist[source][cur][inv] + cc;
            }
        }

        if(cur == antestram.from)
        {
            ll v = antestram.to;
            ll cc = antestram.cost;
            ll ide = antestram.id;

            if(dist[source][v][inv] > dist[source][cur][inv] + cc)
            {
                from_where[source][v][inv] = ide;
                dist[source][v][inv] = dist[source][cur][inv] + cc;
            }
        }
    }

    return;
}

void find_interesting(ll source,ll inv)
{
    rep(i,0,n+1)
    {
        if(i == source)
            continue;

        is_interesting[from_where[source][i][inv]] = true;
    }

    return;
}

ll do_normal(ll id)
{
    ll u = edges[id].from;
    ll v = edges[id].to;
    ll D = edges[id].reverse_cost;
    ll c = edges[id].cost;

    ll goton = min(dist[1][n][0],dist[1][v][0]+dist[n][u][1]+c);
    ll goto1 = min(dist[n][1][0],dist[n][v][0]+dist[1][u][1]+c);

    ll path = goton+goto1;

    return path + D;
}

ll do_interesting(ll id)
{
    antestram = edges[id];
    antestram.from ^= antestram.to;
    antestram.to ^= antestram.from;
    antestram.from ^= antestram.to;

    dijkstra(1,graph,2);
    dijkstra(n,graph,2);

    return dist[1][n][2]+dist[n][1][2]+antestram.reverse_cost;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    rep(i,0,m)
    {
        ll a,b,c,d;
        cin >> a >> b >> c >> d;

        edges.push_back({b,c,d,i,a});

        graph[a].push_back({b,c,d,i});
        inverse[b].push_back({a,c,d,i});
    }

    antestram.from = -1;
    antestram.id = m+2;

    dijkstra(1,graph,0);
    find_interesting(1,0);

    dijkstra(1,inverse,1);
    find_interesting(1,1);

    dijkstra(n,graph,0);
    find_interesting(n,0);

    dijkstra(n,inverse,1);
    find_interesting(n,1);

    ll ans = dist[1][n][0] + dist[n][1][0];

    rep(i,0,m)
    {
        if(is_interesting[i])
            ans=min(ans,do_interesting(i));
        else
            ans = min(ans,do_normal(i));
    }

    if(ans < INF)
        cout << ans << "\n";
    else
        cout << -1 << "\n";

    return 0;
}

/*
4 4
2 1 0 1
4 2 0 2
1 3 0 0
4 1 0 3
*/

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