Submission #125368

#TimeUsernameProblemLanguageResultExecution timeMemory
125368abacabaCeste (COCI17_ceste)C++14
64 / 160
2536 ms131076 KiB
#include <bits/stdc++.h> using namespace std; #define max3(a, b, c) max(a, max(b, c)) #define min3(a, b, c) min(a, min(b, c)) #define mp make_pair #define f first #define se second #define pb push_back #define ppb pop_back #define ll long long #define ull unsigned long long #define cntbit(x) __builtin_popcount(x) #define uset unordered_set #define umap unordered_map #define pii pair<int, int> #define ld long double #define pll pair<long long, long long> struct edge { int to, t, cost; edge(int to, int t, int cost) : to(to), t(t), cost(cost) {} }; const int inf = 2e9; const int N = 2e3 + 15; int n, m, ans[N]; map <int, int> d[N]; vector <edge> g[N]; bool used[N]; void dfs(int v, int t = 0, int cost = 0) { d[v][t] = cost; used[v] = true; for(edge e : g[v]) { if(used[e.to]) continue; if(d[e.to].empty() || d[e.to].find(t + e.t) == d[e.to].end() || d[e.to][t + e.t] > cost + e.cost) dfs(e.to, t + e.t, cost + e.cost); } used[v] = false; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i = 1; i <= m; ++i) { int u, v, t, c; cin >> u >> v >> t >> c; g[u].pb(*new edge(v, t, c)); g[v].pb(*new edge(u, t, c)); } dfs(1); for(int i = 2; i <= n; ++i) { int ans = inf; for(map <int, int>::iterator it = d[i].begin(); it != d[i].end(); ++it) ans = min(ans, it->f * it->se); cout << (ans == inf ? - 1 : ans) << endl; } return 0; }
#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...