# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
382670 |
2021-03-28T02:22:31 Z |
jainbot27 |
Robot (JOI21_ho_t4) |
C++17 |
|
792 ms |
45468 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define F0R(i, n) for(int i=0; i<n; i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define ROF(i, a, b) for(int i=b-1; i>=a; i--)
#define siz(x) (int) x.size()
#define f first
#define s second
#define pb push_back
#define trav(x, v) for(auto& x : v)
const int mxN = 1e5+10;
const ll infLL = 1e18+10;
int n, m;
vector<array<int, 3>> adj[mxN];
ll dist[mxN][2];
int vis[mxN];
int lst[mxN];
priority_queue<pair<ll, pair<int, int> >, vector<pair<ll, pair<int, int>>>, greater<pair<ll, pair<int, int>>>> pq;;
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
F0R(i, n) lst[i] = -1e9;
F0R(i, m){
int a, b, c, d; cin >> a >> b >> c >> d; a--; b--;
adj[a].pb({b, c, d}); adj[b].pb({a, c, d});
}
FOR(i, 1, n) dist[i][0] = dist[i][1] = infLL;
pq.push({0, {0, -1e9}});
while(!pq.empty()){
auto T = pq.top(); pq.pop();
if(vis[T.s.f]==2||(vis[T.s.f]==1&&lst[T.s.f]==T.s.s)) continue;
//cout << T.f << ' ' << T.s.f << ' ' << T.s.s << "\n";
dist[T.s.f][vis[T.s.f]] = T.f;
vis[T.s.f]++;
lst[T.s.f] = T.s.s;
map<int, ll> col;
trav(v, adj[T.s.f]){
if(v[0]==-T.s.s) continue;
if(v[1]!=T.s.s) col[v[1]] += v[2];
}
trav(v, adj[T.s.f]){
if(v[0]==-T.s.s) continue;
if(v[1]!=T.s.s){
pq.push({T.f+col[v[1]]-v[2], {v[0], v[1]}});
}
pq.push({T.f+v[2], {v[0], -T.s.f}});
}
}
cout << (dist[n-1][0]==infLL?-1:dist[n-1][0]) << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2668 KB |
Output is correct |
2 |
Correct |
2 ms |
2668 KB |
Output is correct |
3 |
Correct |
3 ms |
2776 KB |
Output is correct |
4 |
Correct |
3 ms |
2668 KB |
Output is correct |
5 |
Correct |
3 ms |
2796 KB |
Output is correct |
6 |
Correct |
3 ms |
2668 KB |
Output is correct |
7 |
Correct |
4 ms |
3052 KB |
Output is correct |
8 |
Correct |
4 ms |
2924 KB |
Output is correct |
9 |
Incorrect |
9 ms |
3244 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
259 ms |
22236 KB |
Output is correct |
2 |
Correct |
85 ms |
9312 KB |
Output is correct |
3 |
Correct |
478 ms |
39104 KB |
Output is correct |
4 |
Correct |
127 ms |
13916 KB |
Output is correct |
5 |
Incorrect |
792 ms |
45468 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2668 KB |
Output is correct |
2 |
Correct |
2 ms |
2668 KB |
Output is correct |
3 |
Correct |
3 ms |
2776 KB |
Output is correct |
4 |
Correct |
3 ms |
2668 KB |
Output is correct |
5 |
Correct |
3 ms |
2796 KB |
Output is correct |
6 |
Correct |
3 ms |
2668 KB |
Output is correct |
7 |
Correct |
4 ms |
3052 KB |
Output is correct |
8 |
Correct |
4 ms |
2924 KB |
Output is correct |
9 |
Incorrect |
9 ms |
3244 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |