Submission #166759

#TimeUsernameProblemLanguageResultExecution timeMemory
166759theStaticMindCeste (COCI17_ceste)C++14
0 / 160
1534 ms131076 KiB
#include<bits/stdc++.h> #define ii pair<int,int> #define mp make_pair #define pb push_back #define all(x) (x).begin(),(x).end() #define INF 100000000000000000 #define int long long int #define modulo 1000000007 using namespace std; struct data{ mutable int time,cost; data(int x,int y):time(x),cost(y){} bool operator<(const data& A)const{ return time<A.time||(time==A.time&&cost<A.cost); } }; struct Cont : set<data>{ void add(data A){ if(empty()){ insert(A); return; } iterator pre=upper_bound(A); if(pre!=begin()){ pre--; if(pre->cost<=A.cost)return; } iterator curr=insert(A).first; iterator next=curr; next++; while(next!=end()&&next->cost>=A.cost)next=erase(next); } }; vector<Cont> val(2002); vector<int>adj[2002]; vector<pair<ii,ii>>edge; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); // freopen("q.gir","r",stdin); // freopen("q.cik","w",stdout); int n,m; cin>>n>>m; for(int i=0;i<m;i++){ int x,y,t,c; cin>>x>>y>>t>>c; edge.pb({{x,y},{t,c}}); } val[1].add(data(0,0)); for(int q=0;q<=n;q++){ for(int i=0;i<m;i++){ int x,y,t,c; x=edge[i].first.first,y=edge[i].first.second; t=edge[i].second.first,c=edge[i].second.second; for(Cont::iterator itr=val[x].begin();itr!=val[x].end();itr++){ val[y].insert(data(itr->time+t,itr->cost+c)); } swap(x,y); for(Cont::iterator itr=val[x].begin();itr!=val[x].end();itr++){ val[y].insert(data(itr->time+t,itr->cost+c)); } } } for(int i=2;i<=n;i++){ if(val[i].empty())cout<<-1<<"\n"; else { int ans=INF; for(Cont::iterator itr=val[i].begin();itr!=val[i].end();itr++){ ans=min(ans,itr->time*itr->cost); } cout<<ans<<"\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...