제출 #1082397

#제출 시각아이디문제언어결과실행 시간메모리
1082397hahahahaRobot (JOI21_ho_t4)C++17
0 / 100
243 ms135964 KiB
#include <bits/stdc++.h> #define eb emplace_back #define F first #define S second using namespace std; typedef long long ll; typedef pair<ll,ll> pll; const ll MAX=1e6+10; const ll oo=0x3f3f3f3f3f3f3f3f; ll n,m; struct edge{ ll d,clr,cst; edge(ll a,ll b,ll c):d(a),clr(b),cst(c){} }; vector<edge> G[MAX]; vector<pll> G2[MAX*3]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>m; for (int i=0;i<m;i++) { ll a,b,c,p; cin>>a>>b>>c>>p; G[a].eb(b,c,p); G[b].eb(a,c,p); G2[a].eb(b,p); G2[b].eb(a,p); } int now=n; for (int i=1;i<=n;i++) { map<int,vector<pll> > ttl; for (auto eg:G[i]) ttl[eg.clr].eb(eg.d,eg.cst); for (auto [clr,egs]:ttl) { ll ttlw=0; for (auto eg:egs) ttlw+=eg.S; for (auto eg:egs) { G2[i].eb(eg.F,ttlw-eg.S); } } } priority_queue<pll> D; vector<bool> vis(now+1,0); vector<ll> d(now+1,oo); d[1]=0; D.emplace(0,1); while (!D.empty()) { while (!D.empty() and vis[D.top().S]) D.pop(); if (D.empty()) break; int v=D.top().S; D.pop(); vis[v]=true; for (auto [u,w]:G2[v]) { if (!vis[u] and d[v]+w<d[u]) { d[u]=d[v]+w; D.emplace(-d[u],u); } } } cout<<(d[n]==oo?-1:d[n])<<"\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...