제출 #851537

#제출 시각아이디문제언어결과실행 시간메모리
851537JuanRobot (JOI21_ho_t4)C++17
0 / 100
256 ms36776 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define tii tuple<int,int,int> #define pii pair<int,int> const int maxn = 1e5+5, INF=0x3f3f3f3f3f3f3f3f; map<int,int> tot[maxn]; vector<tii> adj[maxn]; int dist[maxn]; void dijkstra(){ priority_queue<pii, vector<pii>, greater<pii>> pq; for(int i=0; i<maxn; i++) dist[i]=INF; pq.push({0,1}); dist[1]=0; while(pq.size()){ auto[d,u] = pq.top(); pq.pop(); if(d>dist[u]) continue; for(auto[b,c,p] : adj[u]){ if(dist[b]>dist[u]+p){ dist[b] = dist[u]+p, pq.push({dist[b], b}); } } } } int32_t main(){ int n, m; cin >> n >> m; for(int i=0; i<m; i++){ int a,b,c,p; cin>>a>>b>>c>>p; adj[a].push_back({b,c,p}); adj[b].push_back({a,c,p}); } for(int i=1; i<=n; i++){ for(auto[b,c,p] : adj[i]) tot[i][c]+=p; for(auto&[b,c,p] : adj[i]) p=min(p,tot[i][c]-p); } dijkstra(); cout << (dist[n]==INF ? -1:dist[n]) << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...