Submission #1245542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245542		AHOKA	Olympic Bus (JOI20_ho_t4)	C++20	16 / 100	85 ms	21228 KiB

ho_t4

#include <bits/stdc++.h>

#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

using namespace std;
 
#define threesum cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
#define all(a) a.begin(), a.end()
#define F first
#define S second
#define int long long
#define pii pair<int, int>
#define ppp pair<int, pii>
#define dout cout << fixed << setprecision(15)
#define mid ((l + r) >> 1)
#define lc (id << 1)
#define rc (lc + 1)

const int maxn = 2e5 + 10, maxm = 2e2 + 10, oo = 1e18, lg = 19, sq = 1400, mod = 998244353;

int n, m, ans;

struct edge{
	int id;
	int u;
	int v;
	int w;
	int c;
} e[maxn];

set<pii> ed[maxm][maxm];

vector<int> in[2][maxn];

int d[maxm][maxm];
bool seen[maxm][maxm];

bool dag[2][maxn];
bool brg[2][maxn];

void djk(int r){
	for (int i = 1; i <= n;i++)
		d[r][i] = oo;
	for (int i = 1; i <= n;i++)
		seen[r][i] = 0;

	d[r][r] = 0;
	for (int j = 1; j <= n;j++){
		int v = 0;

		for (int i = 1; i <= n;i++)
			if(!seen[r][i] && (!v || d[r][v] > d[r][i]))
				v = i;

		seen[r][v] = 1;

        for (int u = 1; u <= n;u++)
            if(!seen[r][u])
                d[r][u] = min(d[r][u], d[r][v] + (*ed[v][u].begin()).F);
    }
}

void solve()
{
	cin >> n >> m;
	for (int i = 1; i <= m;i++){
		cin >> e[i].u >> e[i].v >> e[i].w >> e[i].c;
        e[i].id = i;

        ed[e[i].u][e[i].v].insert({e[i].w, i});
    }

    for (int i = 1; i <= n;i++)
        for (int j = 1; j <= n;j++)
            ed[i][j].insert({oo, 0});

    for (int i = 1; i <= n; i++)
        djk(i);

    for (int b = 0; b < 2; b++)
        for (int i = 1; i <= m; i++)
        {
            int s = (b ? n : 1);
            int t = (b ? 1 : n);
            if ((d[s][e[i].u] + e[i].w + d[e[i].v][t]) == d[s][t])
            {
                in[b][e[i].v].push_back(i);
                dag[b][i] = 1;
            }
        }

	ans = d[1][n] + d[n][1];

    for (int v = 1; v <= n; v++)
        for (int b = 0; b < 2;b++)
            if(in[b][v].size() == 1)
                brg[b][in[b][v][0]] = 1;

    for (int i = 1; i <= m;i++){
        if((!brg[0][i] || (d[1][n] >= oo)) && (!brg[1][i] || (d[n][1] >= oo))){
            // e[i].u -> e[i].v
            // e[i].v -> e[i].u

            int go = min(d[1][n], d[1][e[i].v] + e[i].w + d[e[i].u][n]);
            int come = min(d[n][1], d[n][e[i].v] + e[i].w + d[e[i].u][1]);

            ans = min(ans, e[i].c + go + come);
        }
    }

    for (int i = 1; i <= m;i++)
        if((brg[0][i] ^ brg[1][i])){
            ed[e[i].u][e[i].v].erase({e[i].w, i});
            swap(e[i].u, e[i].v);
            ed[e[i].u][e[i].v].insert({e[i].w, i});

            djk(1);
            djk(n);

            ans = min(ans, d[1][n] + d[n][1] + e[i].c);

            ed[e[i].u][e[i].v].erase({e[i].w, i});
            swap(e[i].u, e[i].v);
            ed[e[i].u][e[i].v].insert({e[i].w, i});
        }

    cout << (ans >= oo? -1 : ans);
}

signed main()
{
    threesum;
    int t = 1;
    //cin >> t;
    while(t--)
        solve();
}

/*
10 87
9 23 33 38 42 44 45 62 67 78
15 91 7 27 31 53 12 91 89 46
*/

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