Submission #201505

#	Time	Username	Problem	Language	Result	Execution time	Memory
201505		Noam527	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	96 ms	3812 KiB

ho_t4

#include <bits/stdc++.h>
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 4e16;
const int OO = 0;
const int OOO = 1;
using namespace std;

struct edge {
	int v, w, i;
	edge() {}
	edge(int vv, int ww, int ii) {
		v = vv;
		w = ww;
		i = ii;
	}
	bool operator < (const edge &a) const {
		return w > a.w;
	}
};

int n, m;
vector<pair<int, int>> e;
vector<int> c, d;
vector<vector<edge>> g;
vector<ll> cost;

vector<int> dist, to;
vector<int> path1, path2;
vector<int> P1, P2; // P1[i] == j if edge i is used as the jth edge (1-indexed), 0 otherwise

// floyd warshall; normal, without p1, without p2
int fw[202][202], fwp1[202][202], fwp2[202][202];

vector<int> dijkstra(int s, int t) {
	for (auto &i : dist)
		i = -1;
	priority_queue<edge> q;
	q.push(edge(s, 0, -1));
	while (q.size()) {
		edge x = q.top();
		q.pop();
		if (dist[x.v] != -1) continue;
		dist[x.v] = x.w;
		to[x.v] = x.i;
		for (const auto &i : g[x.v])
			if (dist[i.v] == -1)
				q.push(edge(i.v, x.w + i.w, i.i));
	}
	if (dist[t] == -1) return{};
	vector<int> res;
	int cur = t;
	while (cur != s) {
		res.push_back(to[cur]);
		cur = e[to[cur]].first;
	}
	reverse(res.begin(), res.end());
	return res;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	e.resize(m), c.resize(m), d.resize(m);
	g.resize(n);
	cost.resize(m, 0);
	dist.resize(n), to.resize(n);
	P1.resize(m, 0), P2.resize(m, 0);

	for (int i = 0; i < m; i++) {
		cin >> e[i].first >> e[i].second >> c[i] >> d[i];
		e[i].first--, e[i].second--;
		g[e[i].first].push_back(edge(e[i].second, c[i], i));
	}

	path1 = dijkstra(0, n - 1), path2 = dijkstra(n - 1, 0);
	for (int i = 0; i < path1.size(); i++)
		P1[path1[i]] = i + 1;
	for (int i = 0; i < path2.size(); i++)
		P2[path2[i]] = i + 1;

	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
		if (i != j)
			fw[i][j] = fwp1[i][j] = fwp2[i][j] = md;
		else
			fw[i][j] = fwp1[i][j] = fwp2[i][j] = 0;
	}
	for (int i = 0; i < m; i++) {
		fw[e[i].first][e[i].second] = min(fw[e[i].first][e[i].second], c[i]);
		if (!P1[i])
			fwp1[e[i].first][e[i].second] = min(fwp1[e[i].first][e[i].second], c[i]);
		if (!P2[i])
			fwp2[e[i].first][e[i].second] = min(fwp2[e[i].first][e[i].second], c[i]);
	}
	for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
		fw[i][j] = min(fw[i][j], fw[i][k] + fw[k][j]);
		fwp1[i][j] = min(fwp1[i][j], fwp1[i][k] + fwp1[k][j]);
		fwp2[i][j] = min(fwp2[i][j], fwp2[i][k] + fwp2[k][j]);
	}

	if (OO) {
		cout << "fw\n";
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) cout << fw[i][j] << " "; cout << '\n';
		}
		cout << "fwp1\n";
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) cout << fwp1[i][j] << " "; cout << '\n';
		}
		cout << "fwp2\n";
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) cout << fwp2[i][j] << " "; cout << '\n';
		}
		cout << "path1:\n";
		for (const auto &i : path1) cout << i << " "; cout << '\n';
		cout << "path2:\n";
		for (const auto &i : path2) cout << i << " "; cout << '\n';
	}

	// costs for path 1
	for (int i = 0; i < m; i++) {
		int u = e[i].first, v = e[i].second;
		if (!P1[i]) {
			if (fw[0][v] == md || fw[u][n - 1] == md) {
				if (fw[0][n - 1] == md)
					cost[i] += inf;
				else
					cost[i] += fw[0][n - 1];
			}
			else if (fw[0][n - 1] == md)
				cost[i] += fw[0][v] + c[i] + fw[u][n - 1];
			else
				cost[i] += min(fw[0][n - 1], fw[0][v] + c[i] + fw[u][n - 1]);
		}
		else {
			int best = md;
			for (int l = 0; l < P1[i]; l++) for (int r = P1[i]; r <= path1.size(); r++) {
				u = e[path1[l]].first, v = e[path1[r - 1]].second;
				if (fw[0][u] != md && fwp1[u][v] != md && fw[v][n - 1] != md)
					best = min(best, fw[0][u] + fwp1[u][v] + fw[v][n - 1]);
			}
			if (best == md)
				cost[i] += inf;
			else
				cost[i] += best;
		}
	}

	// same thing for path 2
	for (int i = 0; i < m; i++) {
		int u = e[i].first, v = e[i].second;
		if (!P2[i]) {
			if (fw[n - 1][v] == md || fw[u][0] == md) {
				if (fw[n - 1][0] == md)
					cost[i] += inf;
				else
					cost[i] += fw[n - 1][0];
			}
			else if (fw[n - 1][0] == md)
				cost[i] += fw[n - 1][v] + c[i] + fw[u][0];
			else
				cost[i] += min(fw[n - 1][0], fw[n - 1][v] + c[i] + fw[u][0]);
		}
		else {
			int best = md;
			for (int l = 0; l < P2[i]; l++) for (int r = P2[i]; r <= path2.size(); r++) {
				u = e[path2[l]].first, v = e[path2[r - 1]].second;
				if (fw[n - 1][u] != md && fwp2[u][v] != md && fw[v][0] != md)
					best = min(best, fw[n - 1][u] + fwp2[u][v] + fw[v][0]);
			}
			if (best == md)
				cost[i] += inf;
			else
				cost[i] += best;
		}
	}

	ll ans = inf;
	if (fw[0][n - 1] != md && fw[n - 1][0] != md)
		ans = min(ans, (ll)fw[0][n - 1] + fw[n - 1][0]);
	for (int i = 0; i < m; i++)
		ans = min(ans, cost[i] + d[i]);
	if (ans > 2 * md)
		cout << "-1\n";
	else
		cout << ans << '\n';
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:79:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < path1.size(); i++)
                  ~~^~~~~~~~~~~~~~
ho_t4.cpp:81:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < path2.size(); i++)
                  ~~^~~~~~~~~~~~~~
ho_t4.cpp:106:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for (int j = 0; j < n; j++) cout << fw[i][j] << " "; cout << '\n';
    ^~~
ho_t4.cpp:106:57: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    for (int j = 0; j < n; j++) cout << fw[i][j] << " "; cout << '\n';
                                                         ^~~~
ho_t4.cpp:110:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for (int j = 0; j < n; j++) cout << fwp1[i][j] << " "; cout << '\n';
    ^~~
ho_t4.cpp:110:59: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    for (int j = 0; j < n; j++) cout << fwp1[i][j] << " "; cout << '\n';
                                                           ^~~~
ho_t4.cpp:114:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for (int j = 0; j < n; j++) cout << fwp2[i][j] << " "; cout << '\n';
    ^~~
ho_t4.cpp:114:59: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    for (int j = 0; j < n; j++) cout << fwp2[i][j] << " "; cout << '\n';
                                                           ^~~~
ho_t4.cpp:117:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : path1) cout << i << " "; cout << '\n';
   ^~~
ho_t4.cpp:117:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : path1) cout << i << " "; cout << '\n';
                                                 ^~~~
ho_t4.cpp:119:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : path2) cout << i << " "; cout << '\n';
   ^~~
ho_t4.cpp:119:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : path2) cout << i << " "; cout << '\n';
                                                 ^~~~
ho_t4.cpp:139:58: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int l = 0; l < P1[i]; l++) for (int r = P1[i]; r <= path1.size(); r++) {
                                                        ~~^~~~~~~~~~~~~~~
ho_t4.cpp:168:58: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int l = 0; l < P2[i]; l++) for (int r = P2[i]; r <= path2.size(); r++) {
                                                        ~~^~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 63 / 63