oj.uz

Submission #243949

# Submission time Handle Problem Language Result Execution time Memory
243949 2020-07-02T10:57:25 Z pit4h Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 1000 ms 3320 KB 
#include<bits/stdc++.h>
using namespace std;

const int N = 201, M = 5e4+1;
const int INF = 1e9+1;
int n, m, u[M], v[M];
long long c[M], d[M];
long long G[N][N], W[N][N];
pair<long long, int> shortest[N][2];

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(G[p][u[i]] + W[u[i]][v[i]] + G[v[i]][q] > G[p][q]) path[0] = G[p][q];
		else for(int j=1; j<=n; ++j) {
			if(G[p][j] > G[p][u[i]]) continue;
			for(int k=1; k<=n; ++k) { if(k==j) continue;
				if(G[k][q] >= G[u[i]][q] || (j==u[i] && k==v[i])) continue;
				path[0] = min(path[0], G[p][j] + W[j][k] + G[k][q]);	
			}
		}	
		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;
		}
		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]);
	}

	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]);	
			}
		}
	}

	for(int i=1; i<=n; ++i) {
		shortest[i][0] = shortest[i][1] = make_pair(INF, 0);
		for(int j=1; j<=n; ++j) {
			if(i==j) continue;
			int path = G[1][i] + W[i][j] + G[j][n];
			if(path <= shortest[i][0].first) {
				shortest[i][1] = shortest[i][0];
				shortest[i][0] = {path, j};
			}
			else if(path < shortest[i][1].first) {
				shortest[i][1] = {path, j};
			}
		}
	}

	
	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 118 ms 1024 KB Output is correct
2 Correct 19 ms 1024 KB Output is correct
3 Correct 15 ms 1024 KB Output is correct
4 Correct 14 ms 1024 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 13 ms 1024 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Incorrect 5 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3192 KB Output is correct
2 Correct 34 ms 3064 KB Output is correct
3 Correct 39 ms 3320 KB Output is correct
4 Incorrect 14 ms 1024 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 1024 KB Output is correct
2 Correct 23 ms 1024 KB Output is correct
3 Execution timed out 1087 ms 2560 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 1024 KB Output is correct
2 Correct 19 ms 1024 KB Output is correct
3 Correct 15 ms 1024 KB Output is correct
4 Correct 14 ms 1024 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 13 ms 1024 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Incorrect 5 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -