제출 #583512

#제출 시각아이디문제언어결과실행 시간메모리
583512AngusWongRobot (JOI21_ho_t4)C++17
0 / 100
607 ms34980 KiB
#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){ cnt[i.f][i.s]--; 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...