oj.uz

Submission #244275

# Submission time Handle Problem Language Result Execution time Memory
244275 2020-07-03T13:08:59 Z pit4h Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 226 ms 4216 KB 
#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();
			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();
			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 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] = G[q][v[i]] + c[i] + d[i] + skip[u[i]][v[i]][p==n];
		path[0] = INF;
		
		if(E[u[i]][v[i]][0] != c[i]) {
			path[0] = min(path[0], G[p][u[i]] + E[u[i]][v[i]][0] + G[v[i]][q]);
		}
		else {
			path[0] = min(path[0], G[p][u[i]] + E[u[i]][v[i]][1] + G[v[i]][q]);
		}
		if(G[p][u[i]] + W[u[i]][v[i]] + G[v[i]][q] > G[p][q]) 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]);
				}
			}
		}
		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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 2992 KB Output is correct
2 Correct 20 ms 3072 KB Output is correct
3 Correct 83 ms 2936 KB Output is correct
4 Correct 81 ms 2936 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 27 ms 2936 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 82 ms 2936 KB Output is correct
11 Correct 82 ms 2956 KB Output is correct
12 Incorrect 85 ms 2944 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 4216 KB Output is correct
2 Correct 226 ms 4088 KB Output is correct
3 Correct 221 ms 4096 KB Output is correct
4 Correct 83 ms 2936 KB Output is correct
5 Correct 68 ms 2944 KB Output is correct
6 Correct 33 ms 2944 KB Output is correct
7 Correct 17 ms 2816 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Incorrect 101 ms 4088 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 2936 KB Output is correct
2 Correct 34 ms 2936 KB Output is correct
3 Correct 120 ms 3832 KB Output is correct
4 Correct 27 ms 2936 KB Output is correct
5 Correct 131 ms 4088 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Incorrect 90 ms 4088 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 2992 KB Output is correct
2 Correct 20 ms 3072 KB Output is correct
3 Correct 83 ms 2936 KB Output is correct
4 Correct 81 ms 2936 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 27 ms 2936 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 82 ms 2936 KB Output is correct
11 Correct 82 ms 2956 KB Output is correct
12 Incorrect 85 ms 2944 KB Output isn't correct
13 Halted 0 ms 0 KB -