제출 #1036059

#제출 시각아이디문제언어결과실행 시간메모리
1036059HNa_seawjingRobot (JOI21_ho_t4)C++14
0 / 100
77 ms26368 KiB
#include <bits/stdc++.h> //code #define fl(i,x,y,z) for(int i=x;i<=y;i=i+z) #define fn(i,x,y,z) for(int i=x;i>=y;i=i-z) #define rep(i,x,y) for(int i=x;i<y;i=i+1) #define all(v) v.begin(),v.end() #define pb push_back #define tle cout<<"tle"<<endl #define edl cout<<"\n" #define el "\n" #define getbit(x,i) ((x>>i)&1) #define bitcnt __builtin_popcount //ham #define pii pair<long long,long long> #define fi first #define se second #define ll long long #define ld long double #define inf 0x3f3f3f3f //#define int long long using namespace std; const ll mod=1e9+7; int n,m; struct kb { int v,c,p; }; vector <kb> e[100005]; vector <pii> a[100005]; int cnt[1000005],t[1000005]; ll d[1000005]; priority_queue <pii,vector <pii>, greater <pii>> q; void inp() { cin>>n>>m; fl(i,1,m,1) { int u,v,c,p; cin>>u>>v>>c>>p; e[u].pb({v,c,p}); e[v].pb({u,c,p}); } } void dij() { fl(i,1,n,1) d[i]=1e18; d[1]=0; q.push({d[1],1}); while (!q.empty()) { int u=q.top().se; int c=q.top().fi; q.pop(); if (c<d[u]) continue; for (auto it: a[u]) { int v=it.fi,w=it.se; if (d[v]>d[u]+w) { d[v]=d[u]+w; q.push({d[v],v}); } } } if (d[n]==1e18) cout<<-1; else cout<< d[n]; } void sol() { fl(u,1,n,1) { for (auto it: e[u]) cnt[it.c]++; for (auto it: e[u]) { int v=it.v,c=it.c,p=it.p; if (cnt[c]>1) { t[c]++; a[u].pb({v,p}); } else { t[c]++; a[u].pb({v,0}); } if (t[c]==cnt[c]) { t[c]=0; cnt[c]=0; } // cout<<cnt[c]<< " "<<u<<" "<<v<<el; } } dij(); } signed main() { // freopen("task.inp","r",stdin); // freopen("task.out","w",stdout); ios_base::sync_with_stdio(false); cin.tie(NULL); inp(); sol(); return 0; } /* /\_/\ ( ._. ) / >V< \ */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...