oj.uz

Submission #244260

# Submission time Handle Problem Language Result Execution time Memory
244260 2020-07-03T12:31:54 Z pit4h Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 145 ms 4608 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];
				}
			}
		}
	}
}

long long solve(int p, int q) {

	long long ans = INF;

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

		long long path[2] = {0, 0};
		path[1] = G[q][v[i]] + c[i] + d[i] + G[u[i]][p];
		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 55 ms 2304 KB Output is correct
2 Correct 24 ms 2304 KB Output is correct
3 Correct 57 ms 2304 KB Output is correct
4 Correct 57 ms 2304 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 27 ms 2304 KB Output is correct
7 Correct 4 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 57 ms 2304 KB Output is correct
11 Correct 59 ms 2304 KB Output is correct
12 Incorrect 56 ms 2304 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 4472 KB Output is correct
2 Correct 131 ms 4472 KB Output is correct
3 Correct 133 ms 4608 KB Output is correct
4 Correct 58 ms 2392 KB Output is correct
5 Correct 47 ms 2304 KB Output is correct
6 Correct 58 ms 2304 KB Output is correct
7 Correct 14 ms 2304 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Incorrect 74 ms 4600 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2304 KB Output is correct
2 Correct 31 ms 2304 KB Output is correct
3 Correct 100 ms 3960 KB Output is correct
4 Correct 30 ms 2424 KB Output is correct
5 Correct 109 ms 4448 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Incorrect 86 ms 4344 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 2304 KB Output is correct
2 Correct 24 ms 2304 KB Output is correct
3 Correct 57 ms 2304 KB Output is correct
4 Correct 57 ms 2304 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 27 ms 2304 KB Output is correct
7 Correct 4 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 57 ms 2304 KB Output is correct
11 Correct 59 ms 2304 KB Output is correct
12 Incorrect 56 ms 2304 KB Output isn't correct
13 Halted 0 ms 0 KB -