답안 #447963

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
447963	2021-07-28T09:35:19 Z	maomao90	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	281 ms	3248 KB

ho_t4

#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifdef DEBUG
#define debug(args...) _debug(args)
void _debug(const char* format, ...) {
	va_list args;
	va_start(args, format);
	vprintf(format, args);
	va_end(args);
}
#else
#define debug(args...)
#endif

#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 205
#define MAXM 50005

int n, m;
ll g[MAXN][MAXN], sg[MAXN][MAXN];
int u[MAXM], v[MAXM], c[MAXM], d[MAXM];
ll rdist[MAXN][MAXN];

bool visited[MAXN];
bool onshot[MAXN][MAXN];
ll dist[MAXN][MAXN];
int p[MAXN];
void dij(int s, bool up = 0) {
	REP (i, 1, n + 1) {
		dist[s][i] = LINF;
		visited[i] = 0;
		p[i] = -1;
	}
	dist[s][s] = 0;
	REP (_, 0, n) {
		ll u = -1, mn = LINF;
		REP (i, 1, n + 1) {
			if (!visited[i] && mnto(mn, dist[s][i])) {
				u = i;
			}
		}
		if (u == -1) break;
		visited[u] = 1;
		REP (i, 1, n + 1) {
			if (mnto(dist[s][i], dist[s][u] + g[u][i]) && up) {
				onshot[u][i] = 1;
				if (p[i] != -1) {
					onshot[p[i]][i] = 0;
				}
				p[i] = u;
			}
		}
	}
}

int main() {
	scanf("%d%d", &n, &m);
	REP (i, 1, n + 1) {
		REP (j, 1, n + 1) {
			g[i][j] = LINF;
			sg[i][j] = LINF;
			rdist[i][j] = LINF;
		}
		g[i][i] = 0;
		sg[i][i] = 0;
	}
	REP (i, 0, m) {
		scanf("%d%d%d%d", &u[i], &v[i], &c[i], &d[i]);
		if (c[i] <= g[u[i]][v[i]]) {
			sg[u[i]][v[i]] = g[u[i]][v[i]];
			g[u[i]][v[i]] = c[i];
		} else {
			mnto(sg[u[i]][v[i]], (ll) c[i]);
		}
	}
	REP (i, 1, n + 1) {
		REP (j, 1, n + 1) {
			rdist[i][j] = g[i][j];
		}
	}
	REP (k, 1, n + 1) {
		REP (i, 1, n + 1) {
			REP (j, 1, n + 1) {
				mnto(rdist[i][j], rdist[i][k] + rdist[k][j]);
			}
		}
	}
	dij(1, 1);
	dij(n, 1);
	ll ans = dist[1][n] + dist[n][1];
	int cnt = 0;
	REP (i, 0, m) {
		ll fi = min(dist[1][n], rdist[1][v[i]] + rdist[u[i]][n] + c[i]),
		   se = min(dist[n][1], rdist[n][v[i]] + rdist[u[i]][1] + c[i]);
		debug("%d %d: %lld %lld\n", u[i], v[i], fi, se);
		if (sg[u[i]][v[i]] != g[u[i]][v[i]] && onshot[u[i]][v[i]] &&
			   	g[u[i]][v[i]] == c[i]) {
			cnt++;
			g[u[i]][v[i]] = sg[u[i]][v[i]];
			ll tmp = g[v[i]][u[i]];
			mnto(g[v[i]][u[i]], (ll) c[i]);
			dij(1);
			dij(n);
			fi = dist[1][n];
			se = dist[n][1];
			g[u[i]][v[i]] = c[i];
			g[v[i]][u[i]] = tmp;
			dij(1);
			dij(n);
		}
		debug("%lld %lld\n", fi, se);
		mnto(ans, fi + se + d[i]);
	}
	assert(cnt <= 2 * n);
	if (ans < LINF) {
		printf("%lld\n", ans);
	} else {
		printf("-1\n");
	}
	return 0;
}

Compilation message

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
ho_t4.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |   scanf("%d%d%d%d", &u[i], &v[i], &c[i], &d[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	136 ms	1356 KB	Output is correct
2	Correct	14 ms	1288 KB	Output is correct
3	Correct	202 ms	1348 KB	Output is correct
4	Correct	212 ms	1332 KB	Output is correct
5	Correct	2 ms	460 KB	Output is correct
6	Correct	14 ms	1228 KB	Output is correct
7	Correct	0 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	174 ms	1336 KB	Output is correct
11	Correct	217 ms	1336 KB	Output is correct
12	Correct	211 ms	1336 KB	Output is correct
13	Correct	66 ms	1348 KB	Output is correct
14	Correct	147 ms	1336 KB	Output is correct
15	Correct	133 ms	1356 KB	Output is correct
16	Correct	120 ms	1296 KB	Output is correct

Subtask #2

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	38 ms	1992 KB	Output is correct
2	Correct	45 ms	2088 KB	Output is correct
3	Correct	41 ms	1996 KB	Output is correct
4	Correct	21 ms	1316 KB	Output is correct
5	Correct	19 ms	1296 KB	Output is correct
6	Correct	15 ms	1228 KB	Output is correct
7	Correct	14 ms	1288 KB	Output is correct
8	Correct	0 ms	332 KB	Output is correct
9	Correct	38 ms	2060 KB	Output is correct
10	Correct	37 ms	2020 KB	Output is correct
11	Correct	36 ms	2028 KB	Output is correct
12	Correct	40 ms	2028 KB	Output is correct
13	Correct	37 ms	2016 KB	Output is correct
14	Correct	36 ms	1988 KB	Output is correct

Subtask #3

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	134 ms	1336 KB	Output is correct
2	Correct	32 ms	1320 KB	Output is correct
3	Correct	125 ms	2008 KB	Output is correct
4	Correct	17 ms	1228 KB	Output is correct
5	Correct	117 ms	2076 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct
7	Correct	0 ms	332 KB	Output is correct
8	Correct	55 ms	2052 KB	Output is correct
9	Correct	61 ms	2028 KB	Output is correct
10	Correct	61 ms	2044 KB	Output is correct
11	Correct	57 ms	1976 KB	Output is correct
12	Correct	60 ms	2060 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	0 ms	332 KB	Output is correct
15	Correct	0 ms	332 KB	Output is correct
16	Correct	0 ms	332 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	64 ms	2032 KB	Output is correct
20	Correct	74 ms	2032 KB	Output is correct
21	Correct	78 ms	1996 KB	Output is correct
22	Correct	64 ms	2040 KB	Output is correct

Subtask #4

63.0 / 63.0

#	결과	실행 시간	메모리	Grader output
1	Correct	136 ms	1356 KB	Output is correct
2	Correct	14 ms	1288 KB	Output is correct
3	Correct	202 ms	1348 KB	Output is correct
4	Correct	212 ms	1332 KB	Output is correct
5	Correct	2 ms	460 KB	Output is correct
6	Correct	14 ms	1228 KB	Output is correct
7	Correct	0 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	174 ms	1336 KB	Output is correct
11	Correct	217 ms	1336 KB	Output is correct
12	Correct	211 ms	1336 KB	Output is correct
13	Correct	66 ms	1348 KB	Output is correct
14	Correct	147 ms	1336 KB	Output is correct
15	Correct	133 ms	1356 KB	Output is correct
16	Correct	120 ms	1296 KB	Output is correct
17	Correct	38 ms	1992 KB	Output is correct
18	Correct	45 ms	2088 KB	Output is correct
19	Correct	41 ms	1996 KB	Output is correct
20	Correct	21 ms	1316 KB	Output is correct
21	Correct	19 ms	1296 KB	Output is correct
22	Correct	15 ms	1228 KB	Output is correct
23	Correct	14 ms	1288 KB	Output is correct
24	Correct	0 ms	332 KB	Output is correct
25	Correct	38 ms	2060 KB	Output is correct
26	Correct	37 ms	2020 KB	Output is correct
27	Correct	36 ms	2028 KB	Output is correct
28	Correct	40 ms	2028 KB	Output is correct
29	Correct	37 ms	2016 KB	Output is correct
30	Correct	36 ms	1988 KB	Output is correct
31	Correct	134 ms	1336 KB	Output is correct
32	Correct	32 ms	1320 KB	Output is correct
33	Correct	125 ms	2008 KB	Output is correct
34	Correct	17 ms	1228 KB	Output is correct
35	Correct	117 ms	2076 KB	Output is correct
36	Correct	0 ms	332 KB	Output is correct
37	Correct	0 ms	332 KB	Output is correct
38	Correct	55 ms	2052 KB	Output is correct
39	Correct	61 ms	2028 KB	Output is correct
40	Correct	61 ms	2044 KB	Output is correct
41	Correct	57 ms	1976 KB	Output is correct
42	Correct	60 ms	2060 KB	Output is correct
43	Correct	1 ms	332 KB	Output is correct
44	Correct	0 ms	332 KB	Output is correct
45	Correct	0 ms	332 KB	Output is correct
46	Correct	0 ms	332 KB	Output is correct
47	Correct	1 ms	332 KB	Output is correct
48	Correct	1 ms	332 KB	Output is correct
49	Correct	64 ms	2032 KB	Output is correct
50	Correct	74 ms	2032 KB	Output is correct
51	Correct	78 ms	1996 KB	Output is correct
52	Correct	64 ms	2040 KB	Output is correct
53	Correct	219 ms	2124 KB	Output is correct
54	Correct	241 ms	3052 KB	Output is correct
55	Correct	247 ms	3052 KB	Output is correct
56	Correct	220 ms	1324 KB	Output is correct
57	Correct	186 ms	1356 KB	Output is correct
58	Correct	181 ms	2884 KB	Output is correct
59	Correct	234 ms	2756 KB	Output is correct
60	Correct	266 ms	2756 KB	Output is correct
61	Correct	177 ms	2832 KB	Output is correct
62	Correct	205 ms	2764 KB	Output is correct
63	Correct	263 ms	2828 KB	Output is correct
64	Correct	228 ms	2728 KB	Output is correct
65	Correct	218 ms	2764 KB	Output is correct
66	Correct	281 ms	2760 KB	Output is correct
67	Correct	17 ms	1740 KB	Output is correct
68	Correct	91 ms	3176 KB	Output is correct
69	Correct	86 ms	3140 KB	Output is correct
70	Correct	173 ms	3248 KB	Output is correct
71	Correct	192 ms	3136 KB	Output is correct
72	Correct	178 ms	3140 KB	Output is correct
73	Correct	176 ms	3244 KB	Output is correct
74	Correct	165 ms	3140 KB	Output is correct