제출 #1245585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1245585		AHOKA	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	154 ms	10824 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, ln, ans;

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

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

int d[maxm][maxm];
int par[maxm][maxm];
bool seen[maxm][maxm];
bool brg[2][maxn];

void djk(int r, bool f = 0)
{
    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] > (d[r][v] + (*ed[v][u].begin()).F))){
                d[r][u] = min(d[r][u], d[r][v] + (*ed[v][u].begin()).F);

                if(f)
                    par[r][u] = (*ed[v][u].begin()).S;
            }
    }
}

void mark(int t, int s){
    int id = par[s][t];

    if(!id || t == s)
        return;

    brg[s == n][id] = 1;

    mark(e[id].u, s);
}

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, 1);

    mark(1, n);
    mark(n, 1);

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

    for (int i = 1; i <= m;i++){
        if(!(brg[0][i] || brg[1][i])){
            // 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();
}

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