# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
439826 |
2021-06-30T22:32:27 Z |
Deepesson |
Robot (JOI21_ho_t4) |
C++17 |
|
1002 ms |
72408 KB |
#include <bits/stdc++.h>
#define MAX 101000
typedef std::pair<long long,long long> pii;
typedef std::pair<long long,pii> pip;
std::vector<pip> con[MAX];
std::unordered_map<long long,long long> custao[MAX];
std::map<long long,long long> mamg[MAX];
int main()
{
int N,M;
std::cin>>N>>M;
for(int i=0;i!=M;++i){
long long a,b,c,d;
std::cin>>a>>b>>c>>d;--a;--b;
custao[a][c]+=d;
custao[b][c]+=d;
con[a].push_back({b,{c,d}});
con[b].push_back({a,{c,d}});
}
std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
queue.push({0,0});
bool visitou[N]={};
long long valores[N]={};
long long custo=0;
while(queue.size()){
auto _ = queue.top();
queue.pop();
if(visitou[_.second])continue;
visitou[_.second]=true;
valores[_.second]=_.first;
for(auto&x:con[_.second]){
if(mamg[x.first].find(x.second.first)==mamg[x.first].end())
mamg[x.first][x.second.first]=_.first;
long long ajuda=_.first;
auto it = mamg[_.second].find(x.second.first);
if(it!=mamg[_.second].end())ajuda=it->second;
queue.push({std::min(ajuda+custao[_.second][x.second.first]-x.second.second,_.first+x.second.second),x.first});
}
}
if(!visitou[N-1]){
printf("-1\n");return 0;
}
std::cout<<valores[N-1]<<"\n";
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:24:15: warning: unused variable 'custo' [-Wunused-variable]
24 | long long custo=0;
| ^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12828 KB |
Output is correct |
2 |
Correct |
9 ms |
12876 KB |
Output is correct |
3 |
Correct |
9 ms |
12948 KB |
Output is correct |
4 |
Correct |
9 ms |
12876 KB |
Output is correct |
5 |
Correct |
11 ms |
12944 KB |
Output is correct |
6 |
Correct |
9 ms |
12940 KB |
Output is correct |
7 |
Correct |
10 ms |
13004 KB |
Output is correct |
8 |
Correct |
10 ms |
12956 KB |
Output is correct |
9 |
Correct |
12 ms |
13468 KB |
Output is correct |
10 |
Correct |
12 ms |
13384 KB |
Output is correct |
11 |
Correct |
13 ms |
13344 KB |
Output is correct |
12 |
Correct |
12 ms |
13260 KB |
Output is correct |
13 |
Correct |
12 ms |
13260 KB |
Output is correct |
14 |
Correct |
12 ms |
13260 KB |
Output is correct |
15 |
Correct |
11 ms |
13236 KB |
Output is correct |
16 |
Correct |
12 ms |
13260 KB |
Output is correct |
17 |
Correct |
12 ms |
13212 KB |
Output is correct |
18 |
Correct |
10 ms |
13004 KB |
Output is correct |
19 |
Correct |
11 ms |
13296 KB |
Output is correct |
20 |
Correct |
11 ms |
13208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
276 ms |
30692 KB |
Output is correct |
2 |
Correct |
114 ms |
21564 KB |
Output is correct |
3 |
Correct |
396 ms |
34164 KB |
Output is correct |
4 |
Correct |
200 ms |
25136 KB |
Output is correct |
5 |
Correct |
962 ms |
68420 KB |
Output is correct |
6 |
Correct |
822 ms |
63576 KB |
Output is correct |
7 |
Correct |
556 ms |
54256 KB |
Output is correct |
8 |
Correct |
632 ms |
52180 KB |
Output is correct |
9 |
Correct |
722 ms |
52108 KB |
Output is correct |
10 |
Correct |
448 ms |
40776 KB |
Output is correct |
11 |
Correct |
247 ms |
32528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12828 KB |
Output is correct |
2 |
Correct |
9 ms |
12876 KB |
Output is correct |
3 |
Correct |
9 ms |
12948 KB |
Output is correct |
4 |
Correct |
9 ms |
12876 KB |
Output is correct |
5 |
Correct |
11 ms |
12944 KB |
Output is correct |
6 |
Correct |
9 ms |
12940 KB |
Output is correct |
7 |
Correct |
10 ms |
13004 KB |
Output is correct |
8 |
Correct |
10 ms |
12956 KB |
Output is correct |
9 |
Correct |
12 ms |
13468 KB |
Output is correct |
10 |
Correct |
12 ms |
13384 KB |
Output is correct |
11 |
Correct |
13 ms |
13344 KB |
Output is correct |
12 |
Correct |
12 ms |
13260 KB |
Output is correct |
13 |
Correct |
12 ms |
13260 KB |
Output is correct |
14 |
Correct |
12 ms |
13260 KB |
Output is correct |
15 |
Correct |
11 ms |
13236 KB |
Output is correct |
16 |
Correct |
12 ms |
13260 KB |
Output is correct |
17 |
Correct |
12 ms |
13212 KB |
Output is correct |
18 |
Correct |
10 ms |
13004 KB |
Output is correct |
19 |
Correct |
11 ms |
13296 KB |
Output is correct |
20 |
Correct |
11 ms |
13208 KB |
Output is correct |
21 |
Correct |
276 ms |
30692 KB |
Output is correct |
22 |
Correct |
114 ms |
21564 KB |
Output is correct |
23 |
Correct |
396 ms |
34164 KB |
Output is correct |
24 |
Correct |
200 ms |
25136 KB |
Output is correct |
25 |
Correct |
962 ms |
68420 KB |
Output is correct |
26 |
Correct |
822 ms |
63576 KB |
Output is correct |
27 |
Correct |
556 ms |
54256 KB |
Output is correct |
28 |
Correct |
632 ms |
52180 KB |
Output is correct |
29 |
Correct |
722 ms |
52108 KB |
Output is correct |
30 |
Correct |
448 ms |
40776 KB |
Output is correct |
31 |
Correct |
247 ms |
32528 KB |
Output is correct |
32 |
Correct |
310 ms |
36140 KB |
Output is correct |
33 |
Correct |
345 ms |
32396 KB |
Output is correct |
34 |
Correct |
534 ms |
44920 KB |
Output is correct |
35 |
Correct |
419 ms |
37996 KB |
Output is correct |
36 |
Correct |
441 ms |
46376 KB |
Output is correct |
37 |
Correct |
564 ms |
49612 KB |
Output is correct |
38 |
Correct |
579 ms |
53936 KB |
Output is correct |
39 |
Correct |
396 ms |
35000 KB |
Output is correct |
40 |
Correct |
745 ms |
53440 KB |
Output is correct |
41 |
Correct |
742 ms |
53688 KB |
Output is correct |
42 |
Correct |
747 ms |
54584 KB |
Output is correct |
43 |
Correct |
303 ms |
32008 KB |
Output is correct |
44 |
Correct |
564 ms |
43164 KB |
Output is correct |
45 |
Correct |
552 ms |
48112 KB |
Output is correct |
46 |
Correct |
489 ms |
47684 KB |
Output is correct |
47 |
Correct |
500 ms |
51144 KB |
Output is correct |
48 |
Correct |
1002 ms |
72408 KB |
Output is correct |