# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
575893 |
2022-06-11T13:54:22 Z |
benson1029 |
Robot (JOI21_ho_t4) |
C++14 |
|
1473 ms |
110620 KB |
#include<bits/stdc++.h>
using namespace std;
int n, m;
int a, b, c, p;
vector< pair<int, pair<int,long long> > > v[100005];
map< pair<int,int> , vector< pair< pair<int,int>, long long > > > edg;
int cnt[200005]; long long sum[200005];
priority_queue< pair<long long, pair<int,int> > > pq;
map< pair<int,int>, long long > dis;
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=0; i<m; i++) {
cin >> a >> b >> c >> p;
v[a].push_back({b, {c, p} });
v[b].push_back({a, {c, p} });
}
for(int i=1; i<=n; i++) {
sort(v[i].begin(), v[i].end());
for(auto j:v[i]) {
cnt[j.second.first]++;
sum[j.second.first] += j.second.second;
}
for(auto j:v[i]) {
// case 1: direct
if(cnt[j.second.first] == 1)
edg[{i, 0}].push_back({{j.first, 0}, 0LL});
else
edg[{i, 0}].push_back({{j.first, 0}, j.second.second});
}
for(auto j:v[i]) {
edg[{j.first, 0}].push_back({{i, j.second.first}, 0});
edg[{i, j.second.first}].push_back({{j.first, 0}, sum[j.second.first]-j.second.second});
}
dis[{i, 0}] = 1e18;
for(auto j:v[i]) {
if(cnt[j.second.first] > 0) {
edg[{i, 0}].push_back({{i, j.second.first}, 0});
dis[{i, j.second.first}] = 1e18;
}
cnt[j.second.first] = sum[j.second.first] = 0;
}
}
dis[{1, 0}] = 0;
pq.push({0, {1, 0}});
while(!pq.empty()) {
auto curr = pq.top().second;
if(dis[curr] != -pq.top().first) {
pq.pop();
continue;
}
pq.pop();
if(curr == make_pair(n, 0)) {
cout << dis[curr] << "\n";
return 0;
}
for(auto j: edg[curr]) {
if(dis[curr] + j.second < dis[j.first]) {
dis[j.first] = dis[curr] + j.second;
pq.push({-dis[j.first], j.first});
}
}
}
cout << "-1\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
1 ms |
2672 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2672 KB |
Output is correct |
7 |
Correct |
3 ms |
2952 KB |
Output is correct |
8 |
Correct |
2 ms |
2804 KB |
Output is correct |
9 |
Correct |
8 ms |
3668 KB |
Output is correct |
10 |
Correct |
7 ms |
3632 KB |
Output is correct |
11 |
Correct |
5 ms |
3412 KB |
Output is correct |
12 |
Correct |
6 ms |
3412 KB |
Output is correct |
13 |
Correct |
6 ms |
3484 KB |
Output is correct |
14 |
Correct |
5 ms |
3452 KB |
Output is correct |
15 |
Correct |
5 ms |
3156 KB |
Output is correct |
16 |
Correct |
8 ms |
3412 KB |
Output is correct |
17 |
Correct |
6 ms |
3284 KB |
Output is correct |
18 |
Correct |
3 ms |
3028 KB |
Output is correct |
19 |
Correct |
5 ms |
3332 KB |
Output is correct |
20 |
Correct |
6 ms |
3284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
472 ms |
36476 KB |
Output is correct |
2 |
Correct |
202 ms |
19356 KB |
Output is correct |
3 |
Correct |
272 ms |
41352 KB |
Output is correct |
4 |
Correct |
204 ms |
25652 KB |
Output is correct |
5 |
Correct |
1269 ms |
110372 KB |
Output is correct |
6 |
Correct |
1050 ms |
100436 KB |
Output is correct |
7 |
Correct |
588 ms |
84392 KB |
Output is correct |
8 |
Correct |
1287 ms |
81356 KB |
Output is correct |
9 |
Correct |
1416 ms |
81144 KB |
Output is correct |
10 |
Correct |
802 ms |
59588 KB |
Output is correct |
11 |
Correct |
312 ms |
49100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
1 ms |
2672 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2672 KB |
Output is correct |
7 |
Correct |
3 ms |
2952 KB |
Output is correct |
8 |
Correct |
2 ms |
2804 KB |
Output is correct |
9 |
Correct |
8 ms |
3668 KB |
Output is correct |
10 |
Correct |
7 ms |
3632 KB |
Output is correct |
11 |
Correct |
5 ms |
3412 KB |
Output is correct |
12 |
Correct |
6 ms |
3412 KB |
Output is correct |
13 |
Correct |
6 ms |
3484 KB |
Output is correct |
14 |
Correct |
5 ms |
3452 KB |
Output is correct |
15 |
Correct |
5 ms |
3156 KB |
Output is correct |
16 |
Correct |
8 ms |
3412 KB |
Output is correct |
17 |
Correct |
6 ms |
3284 KB |
Output is correct |
18 |
Correct |
3 ms |
3028 KB |
Output is correct |
19 |
Correct |
5 ms |
3332 KB |
Output is correct |
20 |
Correct |
6 ms |
3284 KB |
Output is correct |
21 |
Correct |
472 ms |
36476 KB |
Output is correct |
22 |
Correct |
202 ms |
19356 KB |
Output is correct |
23 |
Correct |
272 ms |
41352 KB |
Output is correct |
24 |
Correct |
204 ms |
25652 KB |
Output is correct |
25 |
Correct |
1269 ms |
110372 KB |
Output is correct |
26 |
Correct |
1050 ms |
100436 KB |
Output is correct |
27 |
Correct |
588 ms |
84392 KB |
Output is correct |
28 |
Correct |
1287 ms |
81356 KB |
Output is correct |
29 |
Correct |
1416 ms |
81144 KB |
Output is correct |
30 |
Correct |
802 ms |
59588 KB |
Output is correct |
31 |
Correct |
312 ms |
49100 KB |
Output is correct |
32 |
Correct |
329 ms |
36972 KB |
Output is correct |
33 |
Correct |
445 ms |
37572 KB |
Output is correct |
34 |
Correct |
858 ms |
62212 KB |
Output is correct |
35 |
Correct |
667 ms |
50252 KB |
Output is correct |
36 |
Correct |
812 ms |
65080 KB |
Output is correct |
37 |
Correct |
731 ms |
74732 KB |
Output is correct |
38 |
Correct |
544 ms |
86084 KB |
Output is correct |
39 |
Correct |
425 ms |
50388 KB |
Output is correct |
40 |
Correct |
1336 ms |
82616 KB |
Output is correct |
41 |
Correct |
1473 ms |
82764 KB |
Output is correct |
42 |
Correct |
1471 ms |
84828 KB |
Output is correct |
43 |
Correct |
505 ms |
42236 KB |
Output is correct |
44 |
Correct |
548 ms |
62284 KB |
Output is correct |
45 |
Correct |
1138 ms |
70220 KB |
Output is correct |
46 |
Correct |
903 ms |
65964 KB |
Output is correct |
47 |
Correct |
866 ms |
71240 KB |
Output is correct |
48 |
Correct |
1361 ms |
110620 KB |
Output is correct |