oj.uz

Submission #410385

# Submission time Handle Problem Language Result Execution time Memory
410385 2021-05-22T15:41:31 Z ngpin04 Olympic Bus (JOI20_ho_t4) C++14
11 / 100
 48 ms 2116 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 205;
const int M = 5e4 + 5; 
const int oo = 1e9;

vector <int> adj[N];
vector <int> newadj[N];

pair <int, int> edge[M];

int dis[N][N];
int d[N];
int f[M];
int g[M];
int par[N];
int cost[M];
int revcost[M];
int n,m;

bool vis[N];
bool flag[M];
bool mark[N];

template <typename T> 
bool mini(T &a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

void dfs(int u, int p) {
	par[u] = p;
	for (int id : newadj[u]) {
		int v = edge[id].se;
		d[v] = d[u] + cost[id];
		dfs(v, id);
	}
}

void solve(int f[], int s, int t) {
	for (int i = 1; i <= n; i++) {
		vis[i] = mark[i] = false;
		newadj[i].clear();
	}

	for (int i = 1; i <= m; i++)
		flag[i] = false;

	queue <int> q({s});
	vis[s] = true;
	while (q.size()) {
		int u = q.front();
		q.pop();
		for (int id : adj[u]) {
			int v = edge[id].se;
			if (!vis[v] && dis[s][u] + cost[id] == dis[s][v]) {
				vis[v] = true;
				q.push(v);
				newadj[u].push_back(id);
			}
		}
	}

	if (!vis[t]) {
		for (int i = 1; i <= m; i++) 
			f[i] = oo;
		return;	
	}

	d[s] = 0;
	dfs(s, -1);

	for (int u = t; u != s; u = edge[par[u]].fi) {
		flag[par[u]] = true;
		mark[u] = true;
	}
	mark[s] = true;

	for (int i = 1; i <= m; i++)
		f[i] = (flag[i]) ? oo : dis[s][t];

	for (int i = 1; i <= m; i++) if (!flag[i]) {
		int u = edge[i].fi;
		int v = edge[i].se;
		if (dis[s][u] == oo)
			continue;
		int res = dis[s][u] + dis[v][t] + cost[i]; 
		if (mark[v]) {
			for (; v != s && v != u; v = edge[par[v]].fi)
				mini(f[par[v]], res);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
		cin >> edge[i].fi >> edge[i].se >> cost[i] >> revcost[i];
	
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= n; j++)
		if (i != j)
			dis[i][j] = oo;

	for (int i = 1; i <= m; i++)  {
		int u = edge[i].fi;
		int v = edge[i].se;
		mini(dis[u][v], cost[i]); 
		adj[u].push_back(i);
	}

	for (int j = 1; j <= n; j++)
	for (int i = 1; i <= n; i++)
	for (int k = 1; k <= n; k++) 
		mini(dis[i][k], dis[i][j] + dis[j][k]);

	// for (int i = 1; i <= n; i++)
	// for (int j = 1; j <= n; j++)
	// 	cerr << i << " " << j << " " << dis[i][j] << "\n"

	int ans = 2 * oo;
	if (dis[1][n] < oo && dis[n][1] < oo)
		ans = min(ans, dis[1][n] + dis[n][1]);

	solve(f, 1, n);
	solve(g, n, 1);

	// for (int i = 1; i <= m; i++)
	// 	cerr << f[i] << " \n"[i == m];

	// for (int i = 1; i <= m; i++) 
	// 	cerr << g[i] << " \n"[i == m];

	for (int i = 1; i <= m; i++) {
		int u = edge[i].fi;
		int v = edge[i].se;
		int l = f[i];
		int r = g[i];
		if (dis[1][n] > dis[1][v] + dis[u][n] + cost[i]) 
			l = dis[1][v] + dis[u][n] + cost[i];

		if (dis[n][1] > dis[n][v] + dis[u][1] + cost[i])
			r = dis[n][v] + dis[u][1] + cost[i];

		// cerr << i << " " << l << " " << r << "\n";

		if (l < oo && r < oo)
			ans = min(ans, l + r + revcost[i]);
	}

	if (ans == 2 * oo)
		ans = -1;
	cout << ans;
	return 0;	
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 460 KB Output is correct
2 Correct 17 ms 508 KB Output is correct
3 Correct 16 ms 532 KB Output is correct
4 Correct 15 ms 528 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 14 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 17 ms 524 KB Output is correct
11 Correct 17 ms 460 KB Output is correct
12 Incorrect 17 ms 524 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1992 KB Output is correct
2 Correct 39 ms 2016 KB Output is correct
3 Correct 48 ms 1976 KB Output is correct
4 Correct 16 ms 460 KB Output is correct
5 Correct 15 ms 532 KB Output is correct
6 Correct 16 ms 524 KB Output is correct
7 Correct 13 ms 512 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 38 ms 2004 KB Output is correct
10 Correct 38 ms 2004 KB Output is correct
11 Correct 38 ms 2012 KB Output is correct
12 Correct 38 ms 2016 KB Output is correct
13 Correct 38 ms 1972 KB Output is correct
14 Correct 38 ms 2064 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 520 KB Output is correct
2 Correct 13 ms 508 KB Output is correct
3 Correct 30 ms 1612 KB Output is correct
4 Correct 14 ms 508 KB Output is correct
5 Correct 35 ms 2004 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 34 ms 1904 KB Output is correct
9 Correct 35 ms 2116 KB Output is correct
10 Incorrect 34 ms 1988 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 460 KB Output is correct
2 Correct 17 ms 508 KB Output is correct
3 Correct 16 ms 532 KB Output is correct
4 Correct 15 ms 528 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 14 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 17 ms 524 KB Output is correct
11 Correct 17 ms 460 KB Output is correct
12 Incorrect 17 ms 524 KB Output isn't correct
13 Halted 0 ms 0 KB -