oj.uz

Submission #203503

# Submission time Handle Problem Language Result Execution time Memory
203503 2020-02-21T03:46:13 Z abacaba Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 119 ms 3964 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;

int is[2][M];

struct edge {
	int u, v, c, d;
	edge() {
		 u = v = c = d = 0;
	}
};

edge e[M];

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 < 3; ++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 = 1; i <= m; ++i) {
		cin >> e[i].u >> e[i].v >> e[i].c >> e[i].d;
		g[e[i].u].push_back(i);
	}

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

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

	for(int i = 0; i < path1.size(); ++i)
		is[0][path1[i]] = i + 1;
	for(int i = 0; i < path2.size(); ++i)
		is[1][path2[i]] = i + 1;

	calc_distance();

	for(int i = 1; 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 = is[0][i] - 1;
			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 = 1; 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 = is[1][i] - 1;
			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 = 1; 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:83:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:98:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < path1.size(); ++i)
                 ~~^~~~~~~~~~~~~~
ho_t4.cpp:100:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < path2.size(); ++i)
                 ~~^~~~~~~~~~~~~~
ho_t4.cpp:113:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k = j; k < path1.size(); ++k) {
                    ~~^~~~~~~~~~~~~~
ho_t4.cpp:106:31: warning: unused variable 'c' [-Wunused-variable]
   int u = e[i].u, v = e[i].v, c = e[i].c;
                               ^
ho_t4.cpp:130:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k = j; k < path2.size(); ++k) {
                    ~~^~~~~~~~~~~~~~
ho_t4.cpp:123: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 35 ms 2936 KB Output is correct
2 Correct 33 ms 2936 KB Output is correct
3 Correct 46 ms 2936 KB Output is correct
4 Correct 35 ms 2976 KB Output is correct
5 Correct 8 ms 2936 KB Output is correct
6 Correct 34 ms 2936 KB Output is correct
7 Correct 6 ms 2936 KB Output is correct
8 Correct 7 ms 2936 KB Output is correct
9 Correct 7 ms 2936 KB Output is correct
10 Incorrect 41 ms 2936 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 3960 KB Output is correct
2 Correct 110 ms 3960 KB Output is correct
3 Correct 119 ms 3964 KB Output is correct
4 Correct 38 ms 3068 KB Output is correct
5 Correct 38 ms 2936 KB Output is correct
6 Correct 35 ms 2936 KB Output is correct
7 Correct 34 ms 2936 KB Output is correct
8 Incorrect 6 ms 2808 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2936 KB Output is correct
2 Correct 34 ms 2940 KB Output is correct
3 Correct 88 ms 3708 KB Output is correct
4 Correct 35 ms 2940 KB Output is correct
5 Correct 107 ms 3832 KB Output is correct
6 Correct 6 ms 2936 KB Output is correct
7 Correct 6 ms 2936 KB Output is correct
8 Correct 113 ms 3832 KB Output is correct
9 Correct 111 ms 3832 KB Output is correct
10 Incorrect 106 ms 3960 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2936 KB Output is correct
2 Correct 33 ms 2936 KB Output is correct
3 Correct 46 ms 2936 KB Output is correct
4 Correct 35 ms 2976 KB Output is correct
5 Correct 8 ms 2936 KB Output is correct
6 Correct 34 ms 2936 KB Output is correct
7 Correct 6 ms 2936 KB Output is correct
8 Correct 7 ms 2936 KB Output is correct
9 Correct 7 ms 2936 KB Output is correct
10 Incorrect 41 ms 2936 KB Output isn't correct
11 Halted 0 ms 0 KB -