oj.uz

Submission #227171

# Submission time Handle Problem Language Result Execution time Memory
227171 2020-04-26T09:58:14 Z maruii Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 443 ms 2296 KB 
#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];

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;
		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 = 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);
		adj[a][b] = min(adj[a][b], pii(c, i));
	}
	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.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 2056 KB Output is correct
2 Correct 443 ms 2296 KB Output is correct
3 Correct 443 ms 2272 KB Output is correct
4 Correct 31 ms 896 KB Output is correct
5 Correct 22 ms 896 KB Output is correct
6 Correct 19 ms 896 KB Output is correct
7 Correct 17 ms 896 KB Output is correct
8 Incorrect 5 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -