Submission #106833

#TimeUsernameProblemLanguageResultExecution timeMemory
106833amiCeste (COCI17_ceste)C++14
64 / 160
7 ms768 KiB
#include <bits/stdc++.h> #define sz(c) int(c.size()) #define rep(i,a,b) for (int i=a; i<(b); ++i) #define per(i,a,b) for (int i=(b)-1; i>=(a); --i) using namespace std; using ll = long long; struct edge_t { int to,t,c; ll w; }; ll const INFLL=ll(1e18); int const INF=int(1e9); int const MAXN=110; int const MAXT=110; int N,M; vector<edge_t> adj[MAXN]; int res[MAXN]; ll d[MAXN]; tuple<int,int,int> pr[MAXN]; void test(ll x, ll y) { rep(i,0,N) { for (auto &e:adj[i]) e.w=e.t*x + e.c*y; } rep(i,0,N) { d[i]=INFLL; pr[i]={-1,-1,-1}; } d[0]=0; priority_queue<pair<ll,int>> q; q.emplace(0,0); while (!q.empty()) { ll w; int v; tie(w,v)=q.top(); w=-w; q.pop(); if (w!=d[v]) continue; for (auto e:adj[v]) { int u=e.to; if (d[u]>w+e.w) { d[u]=w+e.w; pr[u]={v,e.t,e.c}; q.emplace(-d[u],u); } } } rep(i,1,N) { int v=i,st=0,sc=0; while (v!=-1) { int t,c; tie(v,t,c)=pr[v]; if (v!=-1) { st+=t; sc+=c; } } if (st*sc!=0) { res[i]=min(res[i],st*sc); } } } int main() { cin.tie(0); ios_base::sync_with_stdio(0); cout<<fixed<<setprecision(10); cin>>N>>M; rep(i,0,M) { int u,v,t,c; cin>>u>>v>>t>>c; u--, v--; adj[u].push_back({v,t,c,0}); adj[v].push_back({u,t,c,0}); } rep(i,1,N) res[i]=INF; int const MAXX=1000; rep(x,0,MAXX+1) test(x,MAXX-x); rep(i,1,N) if (res[i]==INF) cout<<"-1\n"; else cout<<res[i]<<"\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...