Submission #227176

#	Time	Username	Problem	Language	Result	Execution time	Memory
227176		maruii	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	520 ms	2808 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second
#define eack emplace_back

int N, M, A[50004], B[50004], U[50004], V[50004], C[50004], D[50004], dist[202][202];
pii adj[202][202], adj2[202][202];

bool vis[202], X[202], Y[202];
vector<pii> edge1[202], edge2[202];
void dfs(int x, int s, vector<pii> edge[]) {
	vis[x] = 1;
	for (int i = 1; i <= N; ++i) if (!vis[i] && dist[s][i] == dist[s][x] + adj[x][i].ff) {
		edge[x].eack(i, adj[x][i].ss);
		dfs(i, s, edge);
	}
}

void dfs0(int x, int e, vector<pii> edge[]) {
	vis[x] = 1;
	for (int i = 1; i <= N; ++i) if (!vis[i] && dist[i][e] == dist[x][e] + adj[i][x].ff) {
		edge[x].eack(i, adj[i][x].ss);
		dfs0(i, e, edge);
	}
}

void dfs1(int x, int ban, vector<pii> edge[]) {
	X[x] = 1;
	for (auto i : edge[x]) if (i.ss != ban) dfs1(i.ff, ban, edge);
}

void dfs2(int x, int ban, vector<pii> edge[]) {
	Y[x] = 1;
	for (auto i : edge[x]) if (i.ss != ban) dfs2(i.ff, ban, edge);
}

void f(int s, int e, int A[]) {
	fill(vis, vis + N + 1, 0);
	dfs(s, s, edge1);
	fill(vis, vis + N + 1, 0);
	dfs0(e, e, edge2);
	for (int i = 0; i < M; ++i) {
		for (int j = 1; j <= N; ++j) X[j] = Y[j] = 0;
		dfs1(s, i, edge1);
		dfs2(e, i, edge2);
		A[i] = 1e9;
		if (adj2[U[i]][V[i]].ff != 1e9) A[i] = min(A[i], dist[s][U[i]] + adj2[U[i]][V[i]].ff + dist[V[i]][e]);
		for (int j = 1; j <= N; ++j) if (X[j] && Y[j]) A[i] = min(A[i], dist[s][j] + dist[j][e]);
		if (X[V[i]] && Y[U[i]]) A[i] = min(A[i], dist[s][V[i]] + C[i] + dist[U[i]][e]);
	}
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) if (i != j) dist[i][j] = adj[i][j].ff = adj2[i][j].ff = 1e9;
	for (int i = 0; i < M; ++i) {
		int a, b, c, d; cin >> a >> b >> c >> d;
		U[i] = a;
		V[i] = b;
		C[i] = c;
		D[i] = d;
		dist[a][b] = min(dist[a][b], c);
		pii t(c, i);
		if (adj[a][b] > t) {
			adj2[a][b] = adj[a][b];
			adj[a][b] = t;
		}
		else if (adj2[a][b] > t) adj2[a][b] = t;
	}
	for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) for (int k = 1; k <= N; ++k) 
		dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);

	f(1, N, A);
	for (int i = 1; i <= N; ++i) edge1[i].clear(), edge2[i].clear();
	f(N, 1, B);

	int ans = 1e9;
	ans = min(ans, dist[1][N] + dist[N][1]);
	for (int i = 0; i < M; ++i) ans = min(ans, D[i] + A[i] + B[i]);
	if (ans == 1e9) ans = -1;
	cout << ans;
	return 0;
}

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