Submission #244317

#	Time	Username	Problem	Language	Result	Execution time	Memory
244317		pit4h	Olympic Bus (JOI20_ho_t4)	C++14	37 / 100	1092 ms	5320 KiB

ho_t4

#include<bits/stdc++.h>
using namespace std;

const int N = 201, M = 5e4+1;
const long long INF = 1e12+1;
int n, m, u[M], v[M];
long long c[M], d[M];
long long G[N][N], W[N][N], E[N][N][2];
long long skip[N][N][2], skipt[N][N][2]; // 0 -> (n, 1), 1 -> (1, n)

void calculate_skip(int p, int q) {
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=n; ++j) {
			skip[i][j][p==1] = INF;
		}
	}
	//calc skip here

	for(int k=1; k<=n; ++k) {
		if(k==q) continue;
		vector<bool> vis(n+1);
		vis[k] = 1;
		priority_queue<pair<long long, int>> Q;
		Q.push({0, q});
		skip[q][k][p==1] = 0;
		while(Q.size()) {
			auto cur = Q.top();
			cur.first *= -1;
			Q.pop();
			if(vis[cur.second]) continue;
			vis[cur.second] = 1;

			for(int i=1; i<=n; ++i) {
				if(i==k) continue;
				if(skip[i][k][p==1] > cur.first + W[i][cur.second]) {
					Q.push({-(cur.first + W[i][cur.second]), i});
					skip[i][k][p==1] = cur.first + W[i][cur.second];
				}
			}
		}
	}

	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=n; ++j) {
			skipt[i][j][p==1] = INF;
		}
	}
	//calc skip here

	for(int k=1; k<=n; ++k) {
		if(k==q) continue;
		vector<bool> vis(n+1);
		vis[k] = 1;
		priority_queue<pair<long long, int>> Q;
		Q.push({0, q});
		skipt[q][k][p==1] = 0;
		while(Q.size()) {
			auto cur = Q.top();
			cur.first *= -1;
			Q.pop();
			if(vis[cur.second]) continue;
			vis[cur.second] = 1;

			for(int i=1; i<=n; ++i) {
				if(i==k) continue;
				if(skipt[i][k][p==1] > cur.first + W[cur.second][i]) {
					Q.push({-(cur.first + W[cur.second][i]), i});
					skipt[i][k][p==1] = cur.first + W[cur.second][i];
				}
			}
		}
	}
}

long long Dist(int U, bool q, int V) {
	if(!q && U == 1) return 0;
	if(q && U == n) return 0;
	long long res = INF;
	for(int i=1; i<=n; ++i) {
		if(i != U && i != V) {
			res = min(res, W[U][i] + skip[i][U][q]);	
		}
	}
	return res;
}

long long DistT(int U, bool q, int V) {
	if(!q && U == 1) return 0;
	if(q && U == n) return 0;
	long long res = INF;
	for(int i=1; i<=n; ++i) {
		if(i != U && i != V) {
			res = min(res, W[i][U] + skipt[i][U][q]);	
		}
	}
	return res;
}

long long solve(int p, int q) {

	long long ans = INF;

	for(int i=0; i<m; ++i) {

		long long path[2] = {0, 0};
// skipt[v[i]][u[i]][p==1]


		path[1] = DistT(v[i], p==1, u[i]) + c[i] + d[i] + Dist(u[i], p==n, v[i]);
		path[0] = INF;
		
		path[0] = min(path[0], DistT(v[i], p==n, u[i]) + c[i] + Dist(u[i], p==1, v[i]));
		
		

		long long replace_edge = INF;
		if(E[u[i]][v[i]][0] != c[i]) {
			replace_edge = E[u[i]][v[i]][0];
			path[0] = min(path[0], G[p][u[i]] + E[u[i]][v[i]][0] + G[v[i]][q]);
		}
		else {
			replace_edge = E[u[i]][v[i]][1];
			path[0] = min(path[0], G[p][u[i]] + E[u[i]][v[i]][1] + G[v[i]][q]);
		}
		if(replace_edge < INF) replace_edge = max(0LL, replace_edge - c[i]);
		if(G[p][u[i]] + c[i] + G[v[i]][q] > G[p][q]) path[0] = min(path[0], G[p][q]);

		else {
			path[0] = min(path[0], skip[p][u[i]][p==1]);
			for(int k=1; k<=n; ++k) {
				if(k != u[i] && k != v[i]) {
					path[0] = min(path[0], G[p][u[i]] + W[u[i]][k] + skip[k][u[i]][p==1]);
				}
			}
		}
		
		path[0] = min(path[0], replace_edge + G[p][v[i]] + c[i] + G[u[i]][q]);

		path[1] = min(path[1], replace_edge + G[q][v[i]] + c[i] + d[i] + G[u[i]][p]);


		ans = min(ans, path[0] + path[1]);
	}
	return ans;
}

int main() {

	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m;

	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=n; ++j) {
			G[i][j] = INF;
			W[i][j] = INF;
			E[i][j][0] = E[i][j][1] = INF;
		}
		G[i][i] = 0;
	}

	for(int i=0; i<m; ++i) {
		cin>>u[i]>>v[i]>>c[i]>>d[i];
		G[u[i]][v[i]] = min(G[u[i]][v[i]], c[i]);
		W[u[i]][v[i]] = min(W[u[i]][v[i]], c[i]);
		if(E[u[i]][v[i]][0] > c[i]) {
			E[u[i]][v[i]][1] = E[u[i]][v[i]][0];
			E[u[i]][v[i]][0] = c[i];
		}
		else if(E[u[i]][v[i]][1] > c[i]) {
			E[u[i]][v[i]][1] = c[i];
		}
	}

	for(int k=1; k<=n; ++k) {
		for(int i=1; i<=n; ++i) {
			for(int j=1; j<=n; ++j) {
				G[i][j] = min(G[i][j], G[i][k] + G[k][j]);	
			}
		}
	}
	
	calculate_skip(1, n);
	calculate_skip(n, 1);

	long long ans = min({G[1][n]+G[n][1], solve(1, n), solve(n, 1)});
	if(ans >= INF) cout<<-1;
	else cout<<ans;
}

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