제출 #1087185

#제출 시각아이디문제언어결과실행 시간메모리
1087185tdkhaiRobot (JOI21_ho_t4)C++14
0 / 100
416 ms61232 KiB
/* K stands for "Khongbietcode" grade 11 computer science Tran Dai Nghia Highschool for the gifted */ #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #define endl '\n' #define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define ll long long #define pb push_back #define ull unsigned long long #define llll pair<ll,ll> #define llllm map<ll,ll> #define gcd(a,b) __gcd(a,b) #define lcm(a,b) a*b/gcd(a,b) #define X first #define Y second #define INF 1LL<<60 using namespace std; using namespace __gnu_pbds; struct edge { ll v,color,w; bool operator > (const edge a) const { return w>a.w; } }; const ll N=1e5+1; vector<edge> a[N]; map<ll,ll> sum[N]; map<ll,ll> cnt[N]; ll d[N]; void solve(){ ll n,m; cin >> n >> m; for(int i=0;i<m;i++) { ll u,v,w,c; cin >> u >> v >> c >> w; a[u].pb({v,c,w}); a[v].pb({u,c,w}); sum[u][c]+=w; sum[v][c]+=w; } for(int i=2;i<=n;i++) { d[i]=INF; } priority_queue< llll,vector<llll>,greater<llll> > pq; pq.push({0,1}); while(pq.size()) { llll top=pq.top(); pq.pop(); // cout << top.Y << '\n'; if(top.X!=d[top.Y]) continue; for(auto i:a[top.Y]) { if(cnt[i.v].find(i.color)==cnt[i.v].end()) { cnt[i.v][i.color]=top.Y; } ll w=top.X; auto f=cnt[top.Y].find(i.color); if(f!=cnt[top.Y].end())w=f->Y; // pq.push({d[top.Y]=min({w+sum[top.Y][i.color]-i.w,top.X+i.Y}),i.v}); if(d[i.v]>min(d[top.Y]+i.w,w+sum[top.Y][i.color]-i.w)) { pq.push({d[i.v]=min(w+sum[top.Y][i.color]-i.w,d[top.Y]+i.w),i.v}); } } } if(d[n]>=INF) { cout << -1; } else { cout << d[n]; } } int main(){ fastIO; // freopen("tdk.inp","r",stdin); // freopen("tdk.out","w",stdout); //freopen("tdk.err","b",stderr); int t=1; //cin>>t; while(t--){ solve(); cout << endl; } // cout << "\n" << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...