# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
583510 |
2022-06-25T13:00:55 Z |
AngusWong |
Robot (JOI21_ho_t4) |
C++17 |
|
530 ms |
38900 KB |
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define f first
#define s second
using namespace std;
ll n, m, x, y, c, p, dist[100001];
vector<pll> v[100001];
map<ll, ll> cnt[100001];
priority_queue<pll, vector<pll>, greater<pll> > pq;
void dij(ll st){
for (int i=1; i<=n; i++) dist[i]=1e18;
dist[st]=0;
pq.push({0, st});
while (!pq.empty()){
pll p=pq.top();
pq.pop();
if (dist[p.s]!=p.f) continue;
for (pll i: v[p.s]){
if (cnt[p.s][i.s]==1){
if (dist[i.f]>p.f){
dist[i.f]=p.f;
pq.push({p.f, i.f});
}
}else{
if (dist[i.f]>p.f+1){
dist[i.f]=p.f+1;
pq.push({p.f+1, i.f});
}
}
}
}
}
int main(){
cin >> n >> m;
for (int i=1; i<=m; i++){
cin >> x >> y >> c >> p;
v[x].push_back({y, c});
v[y].push_back({x, c});
cnt[x][c]++, cnt[y][c]++;
}
dij(1);
if (dist[n]==1e18) cout << "-1\n";
else cout << dist[n] << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7252 KB |
Output is correct |
2 |
Correct |
4 ms |
7352 KB |
Output is correct |
3 |
Incorrect |
5 ms |
7252 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
126 ms |
17560 KB |
Output is correct |
2 |
Correct |
56 ms |
12348 KB |
Output is correct |
3 |
Correct |
167 ms |
20288 KB |
Output is correct |
4 |
Correct |
96 ms |
14284 KB |
Output is correct |
5 |
Incorrect |
530 ms |
38900 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7252 KB |
Output is correct |
2 |
Correct |
4 ms |
7352 KB |
Output is correct |
3 |
Incorrect |
5 ms |
7252 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |