제출 #941917

#제출 시각아이디문제언어결과실행 시간메모리
941917Maite_MoraleRobot (JOI21_ho_t4)C++14
0 / 100
476 ms89336 KiB
#include<bits/stdc++.h> #define F first #define S second #define MAX 500005 #define oo 1e18 #define mod 1000000007 #define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0); using namespace std; typedef long long ll; #define pll pair<ll , ll> #define vll vector<ll> #define vvll vector<vll> #define vpll vector<pll> ll m,n,ans=oo; vll pass[MAX]; map<ll,ll> node[MAX]; vector<pair<ll,pll>> v[MAX]; void distra(ll x,ll y){ priority_queue<pair<ll,pll>> q; q.push({0,{x,0}}); while(!q.empty()){ pair<ll,pll> u=q.top();q.pop(); // cerr<<u.S.F<<" "<<u.S.S<<": "<<-u.F<<"\n"; if(pass[u.S.F][node[u.S.F][u.S.S]]!=0)continue; pass[u.S.F][node[u.S.F][u.S.S]]=1; if(u.S.F==y){ if(ans==oo)ans=-u.F; else ans=min(ans,-u.F); } // if(u.S==y)return -u.F; map<ll,ll> mp; for(auto w : v[u.S.F]){ if(w.F==u.S.S || w.F==0)continue; mp[w.S.F]+=w.S.S; }//cerr<<"."; for(auto w : v[u.S.F]){ if(w.F==u.S.S || w.F==0)continue; // cerr<<" "<<w.F<<" "<<min(w.S.S,mp[w.S.F]-w.S.S)<<"\n"; q.push({u.F-min(w.S.S,mp[w.S.F]-w.S.S),{w.F,u.S.F}}); } } } int main(){ fast_in cin>>n>>m;ll a1=1,a2=0,a3=0,a4=0; node[a1][a2]=v[a1].size(); v[a1].push_back({a2,{a3,a4}}); for(int i=0;i<m;i++){ cin>>a1>>a2>>a3>>a4; node[a1][a2]=v[a1].size(); node[a2][a1]=v[a2].size(); v[a1].push_back({a2,{a3,a4}}); v[a2].push_back({a1,{a3,a4}}); } for(int i=1;i<=n;i++){ pass[i].assign(v[i].size(),0); } distra(1,n); if(ans==oo)cout<<-1; else cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...