Submission #203120

#	Time	Username	Problem	Language	Result	Execution time	Memory
203120		ics0503	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	832 ms	7928 KiB

ho_t4

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
struct xy { long long x, y, z, ck, idx; };
vector<xy>edge[212], redge[212];
long long n, m, dist[4][212], bef[4][212], dep[4][212], rdist[4][212], u[51515], v[51515], c[51515];
void dijkstra(long long st, long long flag, long long dist[4][212], vector<xy> edge[212]) {
	for (int i = 1; i <= n; i++)dist[flag][i] = 1e15;
	dist[flag][st] = 0;
	priority_queue<pair<long long , long long >>H;
	H.push({0, st});
	int dept = 0;
	while (!H.empty()) {
		auto g = H.top(); H.pop();
		long long now = g.second;
		if (dist[flag][now] != -g.first)continue;
		dep[flag][now] = ++dept;
		for (xy E : edge[now]) {
			if (E.ck)continue;
			long long nxt = E.x, c = E.y;
			if (dist[flag][nxt] > dist[flag][now] + c) {
				dist[flag][nxt] = dist[flag][now] + c;
				H.push({ -dist[flag][nxt],nxt });
			}
		}
	}
}
int main() {
	long long i, j; scanf("%lld%lld", &n, &m);
	for (i = 0; i < m; i++) {
		long long d; scanf("%lld%lld%lld%lld", &u[i], &v[i], &c[i], &d);
		edge[u[i]].push_back({ v[i],c[i],d,0,i });
		redge[v[i]].push_back({ u[i],c[i],d,0,i });
	}
	dijkstra(1, 0, dist, edge); dijkstra(n, 1, dist, edge);
	dijkstra(1, 0, rdist, redge); dijkstra(n, 1, rdist, redge);
	for (long long tc = 0; tc < 2; tc++) {
		for (i = 0; i < m; i++) {
			if (dist[tc][u[i]] < 1e14 && dist[tc][u[i]] + c[i] == dist[tc][v[i]] && dep[tc][v[i]] > dep[tc][u[i]]) {
				bef[tc][v[i]] = i + 1;
			}
		}
	}
	long long ans = dist[0][n] + dist[1][1];
	for (i = 1; i <= n; i++) {
		for (j = 0; j < edge[i].size(); j++) {
			long long u = i, v = edge[i][j].x, c = edge[i][j].y, d = edge[i][j].z, idx = edge[i][j].idx;
			if (bef[0][v] != idx + 1 && bef[1][v] != idx + 1) {
				ans = min(ans, dist[0][v] + c + rdist[1][u] + dist[1][1] + d);
				ans = min(ans, dist[1][v] + c + rdist[0][u] + dist[0][n] + d);
				ans = min(ans, dist[0][v] + c + rdist[1][u] + dist[1][v] + c + rdist[0][u] + d);
			}
			else {
				edge[i][j].ck = 1;
				edge[v].push_back({ u, c, d, 0, idx });
				dijkstra(1, 2, dist, edge);
				dijkstra(n, 3, dist, edge);
				ans = min(ans, dist[2][n] + dist[3][1] + d);
				edge[v].pop_back();
				edge[i][j].ck = 0;
			}
		}
	}
	if (ans >= 1e14)printf("-1");
	else printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:48:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (j = 0; j < edge[i].size(); j++) {
               ~~^~~~~~~~~~~~~~~~
ho_t4.cpp:31:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  long long i, j; scanf("%lld%lld", &n, &m);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:33:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   long long d; scanf("%lld%lld%lld%lld", &u[i], &v[i], &c[i], &d);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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