oj.uz

답안 #701335

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
701335 2023-02-21T01:05:26 Z Jasonwei08 Robot (JOI21_ho_t4) C++14
100 / 100
 601 ms 85040 KB 
#include <bits/stdc++.h>
#define int long long
#define re(a, b, c, d) for (auto a = b; a <= c; a += d)
#define de(a, b, c, d) for (auto a = b; a >= c; a -= d)
#define ms (a); memset (a, 0, sizeof a);
#define imax INT_MAX
#define imin INT_MIN
#define wh(a) while (a --)
using namespace std;
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
typedef pair<lint, lint> plint;
const int MAX = 4e5 + 10;
int n, m, d[400005];
vector <int> a;
vector <pair <int, int> > g[400005];
vector <pair <int, pair <int, int> > > v[400005];
signed main () {
//	freopen ("10.in", "r", stdin);
	cin >> n >> m;
	re (i, 0, m - 1, 1) {
		int a, b, c, p;
		cin >> a >> b >> c >> p;
		v[a].push_back ({c, {p, b}});
		v[b].push_back ({c, {p, a}});
	}
	int sz = n;
	for (int i = 1; i < n; i++) {
		if (v[i].empty()) continue;
		sort (v[i].begin(), v[i].end());
		for (int l = 0, r = 0; l < v[i].size(); l = r) {
			lint s = 0;
			while (r < v[i].size() && v[i][l].first == v[i][r].first) s += v[i][r++].second.first;
			if (r - l == 1) g[i].emplace_back (0, v[i][l].second.second);
			else {
				g[i].emplace_back (0, ++sz);
				for (int j = l; j < r; j++) {
					pint x = v[i][j].second;
					g[i].emplace_back  (x);
					g[x.second].emplace_back (0, sz);
					g[sz].emplace_back (s - x.first, x.second);
				}
			}
		}
	}
	priority_queue<pair <int, int> > Q;
	Q.emplace (0, 1);
	for (int i = 1; i <= sz; i++) d[i] = 4e18;
	while (!Q.empty()) {
		auto t = Q.top();
		Q.pop();
		if (d[t.second] != 4e18) continue;
		d[t.second] = -t.first;
		for (auto nxt : g[t.second]) Q.emplace (t.first - nxt.first, nxt.second);
	}
	cout << (d[n] == 4e18 ? -1 : d[n]);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:32:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for (int l = 0, r = 0; l < v[i].size(); l = r) {
      |                          ~~^~~~~~~~~~~~~
Main.cpp:34:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |    while (r < v[i].size() && v[i][l].first == v[i][r].first) s += v[i][r++].second.first;
      |           ~~^~~~~~~~~~~~~

Subtask #1
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 19028 KB Output is correct
2 Correct 10 ms 19028 KB Output is correct
3 Correct 11 ms 19100 KB Output is correct
4 Correct 10 ms 19092 KB Output is correct
5 Correct 10 ms 19096 KB Output is correct
6 Correct 10 ms 19124 KB Output is correct
7 Correct 12 ms 19396 KB Output is correct
8 Correct 11 ms 19228 KB Output is correct
9 Correct 13 ms 19620 KB Output is correct
10 Correct 13 ms 19668 KB Output is correct
11 Correct 13 ms 19796 KB Output is correct
12 Correct 14 ms 19688 KB Output is correct
13 Correct 13 ms 19816 KB Output is correct
14 Correct 13 ms 19744 KB Output is correct
15 Correct 12 ms 19412 KB Output is correct
16 Correct 14 ms 19540 KB Output is correct
17 Correct 13 ms 19492 KB Output is correct
18 Correct 12 ms 19156 KB Output is correct
19 Correct 15 ms 19796 KB Output is correct
20 Correct 13 ms 19396 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 217 ms 42012 KB Output is correct
2 Correct 91 ms 29036 KB Output is correct
3 Correct 361 ms 59100 KB Output is correct
4 Correct 141 ms 33620 KB Output is correct
5 Correct 430 ms 74716 KB Output is correct
6 Correct 495 ms 74256 KB Output is correct
7 Correct 467 ms 81792 KB Output is correct
8 Correct 552 ms 71316 KB Output is correct
9 Correct 588 ms 71352 KB Output is correct
10 Correct 306 ms 50684 KB Output is correct
11 Correct 190 ms 43208 KB Output is correct

Subtask #3
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 19028 KB Output is correct
2 Correct 10 ms 19028 KB Output is correct
3 Correct 11 ms 19100 KB Output is correct
4 Correct 10 ms 19092 KB Output is correct
5 Correct 10 ms 19096 KB Output is correct
6 Correct 10 ms 19124 KB Output is correct
7 Correct 12 ms 19396 KB Output is correct
8 Correct 11 ms 19228 KB Output is correct
9 Correct 13 ms 19620 KB Output is correct
10 Correct 13 ms 19668 KB Output is correct
11 Correct 13 ms 19796 KB Output is correct
12 Correct 14 ms 19688 KB Output is correct
13 Correct 13 ms 19816 KB Output is correct
14 Correct 13 ms 19744 KB Output is correct
15 Correct 12 ms 19412 KB Output is correct
16 Correct 14 ms 19540 KB Output is correct
17 Correct 13 ms 19492 KB Output is correct
18 Correct 12 ms 19156 KB Output is correct
19 Correct 15 ms 19796 KB Output is correct
20 Correct 13 ms 19396 KB Output is correct
21 Correct 217 ms 42012 KB Output is correct
22 Correct 91 ms 29036 KB Output is correct
23 Correct 361 ms 59100 KB Output is correct
24 Correct 141 ms 33620 KB Output is correct
25 Correct 430 ms 74716 KB Output is correct
26 Correct 495 ms 74256 KB Output is correct
27 Correct 467 ms 81792 KB Output is correct
28 Correct 552 ms 71316 KB Output is correct
29 Correct 588 ms 71352 KB Output is correct
30 Correct 306 ms 50684 KB Output is correct
31 Correct 190 ms 43208 KB Output is correct
32 Correct 334 ms 68772 KB Output is correct
33 Correct 300 ms 55348 KB Output is correct
34 Correct 410 ms 61492 KB Output is correct
35 Correct 353 ms 55696 KB Output is correct
36 Correct 397 ms 63352 KB Output is correct
37 Correct 447 ms 72932 KB Output is correct
38 Correct 434 ms 81788 KB Output is correct
39 Correct 423 ms 72420 KB Output is correct
40 Correct 598 ms 72588 KB Output is correct
41 Correct 601 ms 73004 KB Output is correct
42 Correct 538 ms 70728 KB Output is correct
43 Correct 221 ms 46288 KB Output is correct
44 Correct 533 ms 85040 KB Output is correct
45 Correct 445 ms 58060 KB Output is correct
46 Correct 397 ms 55916 KB Output is correct
47 Correct 465 ms 67236 KB Output is correct
48 Correct 530 ms 80936 KB Output is correct