# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
807505 | 2023-08-04T18:25:26 Z | vjudge1 | Robot (JOI21_ho_t4) | C++17 | 3000 ms | 102852 KB |
#include <bits/stdc++.h> using namespace std; #define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define rall(s) s.rbegin(),s.rend() #define all(s) s.begin(),s.end() #define pb push_back #define fi first #define se second #define ll long long #define ld long double #define YES cout<<"YES\n" #define Yes cout<<"Yes\n" #define yes cout<<"yes\n" #define NO cout<<"NO\n" #define No cout<<"No\n" #define no cout<<"no\n" const int N = 1e5 + 9 , mod = 1e9 + 7; ll d[N] = {} , dp[N] = {} , a[N] = {}, b[N] , c[N]; struct edge{ int to , cost; }; set<int>st[N]; map<int,vector<edge>>v[N]; map<int,ll>sum[N] , d1[N]; void solve(){ ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn = 1e18 , mx = 0; cin>>n>>m; for(i = 1; i <= m; i++){ cin>>x>>y>>l>>r; st[x].insert(l); st[y].insert(l); v[x][l].pb({y , r}); v[y][l].pb({x , r}); sum[x][l] += r; sum[y][l] += r; } for(i = 1; i <= n; i++) d[i] = 1e18; set<pair<ll,pair<int,int>>>st; st.insert({0 , {0 , 1}}); d[1] = 0; while(!st.empty()){ x = st.begin()->fi , y = st.begin()->se.se , k = st.begin()->se.fi; st.erase(st.begin()); if(k){ if(d1[y][k] != x) continue; for(auto to : v[y][k]){ z = x + sum[y][k] - to.cost; if(d[to.to] > z){ if(st.find({d[to.to] , {0 , to.to}}) != st.end()) st.erase(st.find({d[to.to] , {0 , to.to}})); d[to.to] = z , st.insert({d[to.to] , {0 , to.to }}); } } }else { if(d[y] != x) continue; for(auto it : ::st[y]){ for(auto to : v[y][it]){ z = to.cost; if(z > sum[y][it] - to.cost) z = sum[y][it] - to.cost; z += x; if(d[to.to] > z){ if(st.find({d[to.to] , {0 , to.to}}) != st.end()) st.erase(st.find({d[to.to] , {0 , to.to}})); d[to.to] = z , st.insert({d[to.to] , {0 , to.to}}); } if(!d1[to.to].count(it) || x < d1[to.to][it]) if(st.find({d1[to.to][it] , {it , to.to}}) != st.end()) st.erase(st.find({d1[to.to][it] , {it , to.to}})); d1[to.to][it] = x; st.insert({d1[to.to][it] , {it, to.to}}); } } } } cout<<(d[n] >= 1e18 ? -1 : d[n])<<"\n"; } int main(){ TL; /* #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif */ int t = 1; //cin>>t; while(t--) { solve(); } } // Author : حسن
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 19028 KB | Output is correct |
2 | Correct | 9 ms | 19028 KB | Output is correct |
3 | Correct | 9 ms | 19100 KB | Output is correct |
4 | Correct | 9 ms | 19128 KB | Output is correct |
5 | Correct | 9 ms | 19124 KB | Output is correct |
6 | Correct | 8 ms | 19028 KB | Output is correct |
7 | Correct | 10 ms | 19284 KB | Output is correct |
8 | Correct | 9 ms | 19156 KB | Output is correct |
9 | Correct | 13 ms | 19928 KB | Output is correct |
10 | Correct | 13 ms | 19796 KB | Output is correct |
11 | Correct | 10 ms | 19540 KB | Output is correct |
12 | Correct | 10 ms | 19412 KB | Output is correct |
13 | Correct | 11 ms | 19484 KB | Output is correct |
14 | Correct | 10 ms | 19508 KB | Output is correct |
15 | Correct | 9 ms | 19416 KB | Output is correct |
16 | Correct | 10 ms | 19340 KB | Output is correct |
17 | Correct | 10 ms | 19412 KB | Output is correct |
18 | Correct | 9 ms | 19336 KB | Output is correct |
19 | Correct | 11 ms | 19344 KB | Output is correct |
20 | Correct | 10 ms | 19412 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 199 ms | 42372 KB | Output is correct |
2 | Correct | 78 ms | 31224 KB | Output is correct |
3 | Correct | 209 ms | 34396 KB | Output is correct |
4 | Correct | 137 ms | 34212 KB | Output is correct |
5 | Correct | 1032 ms | 102852 KB | Output is correct |
6 | Correct | 847 ms | 89232 KB | Output is correct |
7 | Correct | 389 ms | 62176 KB | Output is correct |
8 | Correct | 366 ms | 51844 KB | Output is correct |
9 | Correct | 380 ms | 51848 KB | Output is correct |
10 | Correct | 365 ms | 58196 KB | Output is correct |
11 | Correct | 108 ms | 37324 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 19028 KB | Output is correct |
2 | Correct | 9 ms | 19028 KB | Output is correct |
3 | Correct | 9 ms | 19100 KB | Output is correct |
4 | Correct | 9 ms | 19128 KB | Output is correct |
5 | Correct | 9 ms | 19124 KB | Output is correct |
6 | Correct | 8 ms | 19028 KB | Output is correct |
7 | Correct | 10 ms | 19284 KB | Output is correct |
8 | Correct | 9 ms | 19156 KB | Output is correct |
9 | Correct | 13 ms | 19928 KB | Output is correct |
10 | Correct | 13 ms | 19796 KB | Output is correct |
11 | Correct | 10 ms | 19540 KB | Output is correct |
12 | Correct | 10 ms | 19412 KB | Output is correct |
13 | Correct | 11 ms | 19484 KB | Output is correct |
14 | Correct | 10 ms | 19508 KB | Output is correct |
15 | Correct | 9 ms | 19416 KB | Output is correct |
16 | Correct | 10 ms | 19340 KB | Output is correct |
17 | Correct | 10 ms | 19412 KB | Output is correct |
18 | Correct | 9 ms | 19336 KB | Output is correct |
19 | Correct | 11 ms | 19344 KB | Output is correct |
20 | Correct | 10 ms | 19412 KB | Output is correct |
21 | Correct | 199 ms | 42372 KB | Output is correct |
22 | Correct | 78 ms | 31224 KB | Output is correct |
23 | Correct | 209 ms | 34396 KB | Output is correct |
24 | Correct | 137 ms | 34212 KB | Output is correct |
25 | Correct | 1032 ms | 102852 KB | Output is correct |
26 | Correct | 847 ms | 89232 KB | Output is correct |
27 | Correct | 389 ms | 62176 KB | Output is correct |
28 | Correct | 366 ms | 51844 KB | Output is correct |
29 | Correct | 380 ms | 51848 KB | Output is correct |
30 | Correct | 365 ms | 58196 KB | Output is correct |
31 | Correct | 108 ms | 37324 KB | Output is correct |
32 | Correct | 196 ms | 25440 KB | Output is correct |
33 | Correct | 192 ms | 28852 KB | Output is correct |
34 | Correct | 474 ms | 52820 KB | Output is correct |
35 | Correct | 348 ms | 43736 KB | Output is correct |
36 | Correct | 373 ms | 53052 KB | Output is correct |
37 | Correct | 432 ms | 55276 KB | Output is correct |
38 | Correct | 477 ms | 65812 KB | Output is correct |
39 | Correct | 185 ms | 31016 KB | Output is correct |
40 | Correct | 375 ms | 57164 KB | Output is correct |
41 | Correct | 425 ms | 57424 KB | Output is correct |
42 | Correct | 544 ms | 68812 KB | Output is correct |
43 | Correct | 196 ms | 43196 KB | Output is correct |
44 | Correct | 486 ms | 45624 KB | Output is correct |
45 | Correct | 332 ms | 54100 KB | Output is correct |
46 | Correct | 273 ms | 54036 KB | Output is correct |
47 | Execution timed out | 3079 ms | 55344 KB | Time limit exceeded |
48 | Halted | 0 ms | 0 KB | - |