# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
974834 |
2024-05-03T23:26:11 Z |
imarn |
Robot (JOI21_ho_t4) |
C++14 |
|
960 ms |
84684 KB |
#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define sz(x) (ll)x.size()
#define pp pair<int,pii>
using namespace std;
const int mxn=1e5+5;
map<int,vector<pair<int,ll>>>g[mxn];
map<int,ll>tt[mxn],dp[mxn];
ll d[mxn];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);ll ans=0;
int n,m;cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b,c,p;cin>>a>>b>>c>>p;
g[a][c].pb({b,p});g[b][c].pb({a,p});
tt[a][c]+=p;tt[b][c]+=p;dp[a][c]=dp[b][c]=1e16;
}for(int i=1;i<=n;i++)d[i]=1e16;d[1]=0;
priority_queue<pair<ll,pii>,vector<pair<ll,pii>>,greater<pair<ll,pii>>>pq;
pq.push({0,{1,0}});
while(!pq.empty()){
auto u=pq.top();pq.pop();
if(u.s.s==0&&u.f>d[u.s.f])continue;
if(u.s.s!=0&&u.f>dp[u.s.f][u.s.s])continue;
if(u.s.s==0){
for(auto it:g[u.s.f]){
for(auto v:it.s){
if(dp[v.f][it.f]>u.f)dp[v.f][it.f]=u.f,pq.push({u.f,{v.f,it.f}});
if(d[v.f]>u.f+min(v.s,tt[u.s.f][it.f]-v.s)){
d[v.f]=u.f+min(v.s,tt[u.s.f][it.f]-v.s);pq.push({d[v.f],{v.f,0}});
}
}
}
}
else {
for(auto v : g[u.s.f][u.s.s]){
if(d[v.f]>u.f+tt[u.s.f][u.s.s]-v.s)d[v.f]=u.f+tt[u.s.f][u.s.s]-v.s,pq.push({d[v.f],{v.f,0}});
}
}
}cout<<(d[n]==1e16?-1:d[n]);
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:15:48: warning: unused variable 'ans' [-Wunused-variable]
15 | ios_base::sync_with_stdio(0);cin.tie(0);ll ans=0;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
3 ms |
14940 KB |
Output is correct |
3 |
Correct |
3 ms |
14940 KB |
Output is correct |
4 |
Correct |
4 ms |
15128 KB |
Output is correct |
5 |
Correct |
4 ms |
15196 KB |
Output is correct |
6 |
Correct |
3 ms |
14940 KB |
Output is correct |
7 |
Correct |
5 ms |
15196 KB |
Output is correct |
8 |
Correct |
4 ms |
15196 KB |
Output is correct |
9 |
Correct |
6 ms |
15708 KB |
Output is correct |
10 |
Correct |
7 ms |
15708 KB |
Output is correct |
11 |
Correct |
5 ms |
15452 KB |
Output is correct |
12 |
Correct |
4 ms |
15452 KB |
Output is correct |
13 |
Correct |
6 ms |
15388 KB |
Output is correct |
14 |
Correct |
5 ms |
15452 KB |
Output is correct |
15 |
Correct |
4 ms |
15452 KB |
Output is correct |
16 |
Correct |
5 ms |
15452 KB |
Output is correct |
17 |
Correct |
5 ms |
15708 KB |
Output is correct |
18 |
Correct |
4 ms |
15196 KB |
Output is correct |
19 |
Correct |
5 ms |
15448 KB |
Output is correct |
20 |
Correct |
5 ms |
15452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
165 ms |
35528 KB |
Output is correct |
2 |
Correct |
55 ms |
25424 KB |
Output is correct |
3 |
Correct |
139 ms |
33276 KB |
Output is correct |
4 |
Correct |
96 ms |
28368 KB |
Output is correct |
5 |
Correct |
960 ms |
83764 KB |
Output is correct |
6 |
Correct |
703 ms |
72484 KB |
Output is correct |
7 |
Correct |
296 ms |
56492 KB |
Output is correct |
8 |
Correct |
375 ms |
51268 KB |
Output is correct |
9 |
Correct |
369 ms |
51132 KB |
Output is correct |
10 |
Correct |
284 ms |
50504 KB |
Output is correct |
11 |
Correct |
112 ms |
37456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
3 ms |
14940 KB |
Output is correct |
3 |
Correct |
3 ms |
14940 KB |
Output is correct |
4 |
Correct |
4 ms |
15128 KB |
Output is correct |
5 |
Correct |
4 ms |
15196 KB |
Output is correct |
6 |
Correct |
3 ms |
14940 KB |
Output is correct |
7 |
Correct |
5 ms |
15196 KB |
Output is correct |
8 |
Correct |
4 ms |
15196 KB |
Output is correct |
9 |
Correct |
6 ms |
15708 KB |
Output is correct |
10 |
Correct |
7 ms |
15708 KB |
Output is correct |
11 |
Correct |
5 ms |
15452 KB |
Output is correct |
12 |
Correct |
4 ms |
15452 KB |
Output is correct |
13 |
Correct |
6 ms |
15388 KB |
Output is correct |
14 |
Correct |
5 ms |
15452 KB |
Output is correct |
15 |
Correct |
4 ms |
15452 KB |
Output is correct |
16 |
Correct |
5 ms |
15452 KB |
Output is correct |
17 |
Correct |
5 ms |
15708 KB |
Output is correct |
18 |
Correct |
4 ms |
15196 KB |
Output is correct |
19 |
Correct |
5 ms |
15448 KB |
Output is correct |
20 |
Correct |
5 ms |
15452 KB |
Output is correct |
21 |
Correct |
165 ms |
35528 KB |
Output is correct |
22 |
Correct |
55 ms |
25424 KB |
Output is correct |
23 |
Correct |
139 ms |
33276 KB |
Output is correct |
24 |
Correct |
96 ms |
28368 KB |
Output is correct |
25 |
Correct |
960 ms |
83764 KB |
Output is correct |
26 |
Correct |
703 ms |
72484 KB |
Output is correct |
27 |
Correct |
296 ms |
56492 KB |
Output is correct |
28 |
Correct |
375 ms |
51268 KB |
Output is correct |
29 |
Correct |
369 ms |
51132 KB |
Output is correct |
30 |
Correct |
284 ms |
50504 KB |
Output is correct |
31 |
Correct |
112 ms |
37456 KB |
Output is correct |
32 |
Correct |
89 ms |
29628 KB |
Output is correct |
33 |
Correct |
87 ms |
31044 KB |
Output is correct |
34 |
Correct |
336 ms |
51392 KB |
Output is correct |
35 |
Correct |
261 ms |
42820 KB |
Output is correct |
36 |
Correct |
274 ms |
47040 KB |
Output is correct |
37 |
Correct |
339 ms |
51684 KB |
Output is correct |
38 |
Correct |
293 ms |
60332 KB |
Output is correct |
39 |
Correct |
86 ms |
32976 KB |
Output is correct |
40 |
Correct |
373 ms |
52432 KB |
Output is correct |
41 |
Correct |
362 ms |
52564 KB |
Output is correct |
42 |
Correct |
452 ms |
63664 KB |
Output is correct |
43 |
Correct |
152 ms |
39640 KB |
Output is correct |
44 |
Correct |
296 ms |
45000 KB |
Output is correct |
45 |
Correct |
268 ms |
47712 KB |
Output is correct |
46 |
Correct |
224 ms |
48208 KB |
Output is correct |
47 |
Correct |
253 ms |
49732 KB |
Output is correct |
48 |
Correct |
936 ms |
84684 KB |
Output is correct |