oj.uz

Submission #203501

# Submission time Handle Problem Language Result Execution time Memory
203501 2020-02-21T03:39:48 Z abacaba Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 121 ms 3968 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
 
const long long inf = 2e13;
const int N = 2e2 + 5;
const int M = 5e4 + 5;

int n, m, a[N];
int d[3][N][N];
int cost[M];
int curd[N], p[N];

vector <int> g[N];
vector <int> path1, path2;

priority_queue <pair <long long, long long>> q;

bool is[2][M];

struct edge {
	int u, v, c, d;
};

vector <edge> e;

inline void recover(int v, vector <int> &path) {
	while(p[v] != -1) {
		path.push_back(p[v]);
		v = e[p[v]].u;
	}
	reverse(path.begin(), path.end());
}

inline void dxtra(int s) {
	fill(curd, curd + N, inf);
	fill(p, p + N, -1);
	q.push(make_pair(0, s));
	curd[s] = 0;
	while(!q.empty()) {
		int d = -q.top().first, v = q.top().second;
		q.pop();
		if(d > curd[v])
			continue;
		for(int ind : g[v]) {
			int to = e[ind].v, w = e[ind].c;
			if(curd[to] > curd[v] + w) {
				p[to] = ind;
				curd[to] = curd[v] + w;
				q.push(make_pair(-curd[to], to));
			}
		}
	}
}

inline void calc_distance() {
	for(int i = 0; i < 2; ++i)
		for(int j = 0; j < N; ++j)
			for(int k = 0; k < N; ++k)
				if(j != k)
					d[i][j][k] = inf;
	for(int i = 0; i < m; ++i)
		d[0][e[i].u][e[i].v] = min(d[0][e[i].u][e[i].v], e[i].c);
	for(int k = 1; k <= n; ++k)
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= n; ++j)
				d[0][i][j] = min(d[0][i][j], d[0][i][k] + d[0][k][j]);
	for(int t = 0; t < 2; ++t) {
		for(int i = 0; i < m; ++i)
			if(!is[t][i])
				d[t+1][e[i].u][e[i].v] = min(d[t+1][e[i].u][e[i].v], e[i].c);
		for(int k = 1; k <= n; ++k)
			for(int i = 1; i <= n; ++i)
				for(int j = 1; j <= n; ++j)
					d[t+1][i][j] = min(d[t+1][i][j], d[t+1][i][k] + d[t+1][k][j]);
	}
}

main() {
	cin >> n >> m;
	for(int i = 0; i < m; ++i) {
		int u, v, cc, dd;
		cin >> u >> v >> cc >> dd;
		g[u].push_back(i);
		e.push_back({u, v, cc, dd});
	}

	dxtra(1);
	if(curd[n] != inf)
		recover(n, path1);

	dxtra(n);
	if(curd[1] != inf)
		recover(1, path2);

	for(int ind : path1)
		is[0][ind] = true;
	for(int ind : path2)
		is[1][ind] = true;

	calc_distance();

	for(int i = 0; i < m; ++i) {
		int u = e[i].u, v = e[i].v, c = e[i].c;
		if(!is[0][i])
			cost[i] += min(d[0][1][n], d[0][1][v] + d[0][u][n] + e[i].c);
		else {
			int j = 0;
			for(j = 0; j < path1.size(); ++j)
				if(i == path1[j])
					break;
			int now = inf;
			for(int i = 0; i <= j; ++i) {
				for(int k = j; k < path1.size(); ++k) {
					int u = e[i].u, v = e[k].v;
					now = min(now, d[0][1][u] + d[1][u][v] + d[0][v][n]);
				}
			}
			cost[i] += now;
		}
	}


	for(int i = 0; i < m; ++i) {
		int u = e[i].u, v = e[i].v, c = e[i].c;
		if(!is[1][i])
			cost[i] += min(d[0][n][1], d[0][n][v] + d[0][u][1] + e[i].c);
		else {
			int j = 0;
			for(j = 0; j < path2.size(); ++j)
				if(i == path2[j])
					break;
			int now = inf;
			for(int i = 0; i <= j; ++i)
				for(int k = j; k < path2.size(); ++k) {
					int u = e[i].u, v = e[k].v;
					now = min(now, d[0][n][u] + d[2][u][v] + d[0][v][1]);
				}
			cost[i] += now;
		}
	}

	int ans = d[0][1][n] + d[0][n][1];

	for(int i = 0; i < m; ++i)
		ans = min(ans, cost[i] + e[i].d);

	if(ans >= inf)
		cout << -1 << endl;
	else
		cout << ans << endl;
	return 0;
}

Compilation message

ho_t4.cpp:80:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:110:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j = 0; j < path1.size(); ++j)
               ~~^~~~~~~~~~~~~~
ho_t4.cpp:115:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k = j; k < path1.size(); ++k) {
                    ~~^~~~~~~~~~~~~~
ho_t4.cpp:105:31: warning: unused variable 'c' [-Wunused-variable]
   int u = e[i].u, v = e[i].v, c = e[i].c;
                               ^
ho_t4.cpp:131:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j = 0; j < path2.size(); ++j)
               ~~^~~~~~~~~~~~~~
ho_t4.cpp:136:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k = j; k < path2.size(); ++k) {
                    ~~^~~~~~~~~~~~~~
ho_t4.cpp:126:31: warning: unused variable 'c' [-Wunused-variable]
   int u = e[i].u, v = e[i].v, c = e[i].c;
                               ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1400 KB Output is correct
2 Correct 33 ms 1272 KB Output is correct
3 Correct 34 ms 1400 KB Output is correct
4 Correct 34 ms 1400 KB Output is correct
5 Correct 8 ms 1144 KB Output is correct
6 Correct 33 ms 1272 KB Output is correct
7 Correct 5 ms 1016 KB Output is correct
8 Incorrect 5 ms 1016 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 3940 KB Output is correct
2 Correct 110 ms 3940 KB Output is correct
3 Correct 121 ms 3940 KB Output is correct
4 Correct 38 ms 1400 KB Output is correct
5 Correct 33 ms 1400 KB Output is correct
6 Correct 33 ms 1400 KB Output is correct
7 Correct 32 ms 1272 KB Output is correct
8 Correct 5 ms 1016 KB Output is correct
9 Correct 119 ms 3944 KB Output is correct
10 Correct 120 ms 3948 KB Output is correct
11 Correct 119 ms 3968 KB Output is correct
12 Correct 121 ms 3940 KB Output is correct
13 Incorrect 121 ms 3940 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1400 KB Output is correct
2 Correct 32 ms 1276 KB Output is correct
3 Correct 91 ms 3300 KB Output is correct
4 Correct 37 ms 1272 KB Output is correct
5 Correct 109 ms 3940 KB Output is correct
6 Correct 5 ms 1016 KB Output is correct
7 Incorrect 5 ms 1016 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1400 KB Output is correct
2 Correct 33 ms 1272 KB Output is correct
3 Correct 34 ms 1400 KB Output is correct
4 Correct 34 ms 1400 KB Output is correct
5 Correct 8 ms 1144 KB Output is correct
6 Correct 33 ms 1272 KB Output is correct
7 Correct 5 ms 1016 KB Output is correct
8 Incorrect 5 ms 1016 KB Output isn't correct
9 Halted 0 ms 0 KB -