Submission #410393

#	Time	Username	Problem	Language	Result	Execution time	Memory
410393		ngpin04	Olympic Bus (JOI20_ho_t4)	C++14	32 / 100	43 ms	2972 KiB

ho_t4

#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] + 1;
		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]; 
		while (!mark[u]) 
			u = edge[par[u]].fi;

		if (d[v] < d[u]) 
			continue;

		if (mark[v]) {
			for (; 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
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 0 / 63