Submission #217411

#TimeUsernameProblemLanguageResultExecution timeMemory
217411quocnguyen1012Ceste (COCI17_ceste)C++14
48 / 160
265 ms2160 KiB
#include <bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; typedef pair<int, int> ii; const int maxn = 2005; int U[maxn], V[maxn], T[maxn], C[maxn]; int N, M; vector<int> adj[maxn]; ll dist[maxn]; int last[maxn]; signed main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("A.INP", "r", stdin); freopen("A.OUT", "w", stdout); #endif // LOCAL cin >> N >> M; for(int i = 1; i <= M; ++i){ cin >> U[i] >> V[i] >> T[i] >> C[i]; adj[U[i]].eb(i); adj[V[i]].eb(i); } fill_n(&dist[0], maxn, 1e18); fill_n(&last[0], maxn, 1e9); priority_queue<pair<ii, int>, vector<pair<ii, int>>, greater<pair<ii, int>>> pq; pq.push(mp(mp(0, 0), 1)); dist[1] = 0; last[1] = 0; while(pq.size()){ auto now = pq.top(); pq.pop(); int t = now.fi.fi, c = now.fi.se, u = now.se; if(last[u] < c) continue; last[u] = c; dist[u] = min(dist[u], 1ll * t * c); for(int id : adj[u]){ int v = U[id] + V[id] - u; pq.push(mp(mp(t + T[id], c + C[id]), v)); } } for(int i = 2; i <= N; ++i) cout << dist[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...