oj.uz

Submission #583510

# Submission time Handle Problem Language Result Execution time Memory
583510 2022-06-25T13:00:55 Z AngusWong Robot (JOI21_ho_t4) C++17
0 / 100
 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";
}

Subtask #1
0 / 34.0

# 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 -

Subtask #2
0 / 24.0

# 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 -

Subtask #3
0 / 42.0

# 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 -