Submission #239551

#TimeUsernameProblemLanguageResultExecution timeMemory
239551VimmerCeste (COCI17_ceste)C++14
48 / 160
416 ms760 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //#pragma GCC optimize("unroll-loops") //#pragma GCC optimize("-O3") //#pragma GCC optimize("Ofast") //#pragma GCC optimize("fast-math") //#pragma GCC optimize("no-stack-protector") #define F first #define S second #define sz(x) int(x.size()) #define pb push_back #define N 101001 #define M ll(1e9 + 7) #define inf 1e9 + 1e9 using namespace std; //using namespace __gnu_pbds; typedef long double ld; typedef long long ll; typedef short int si; typedef array <int, 3> a3; //typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; const ld E = 1e-9; vector <int> g[2005]; int A[2005], B[2005], T[2005], C[2005]; int opr(int i, int b) {return (A[i] == b ? B[i] : A[i]);} set <pair <ld, int> > se; ll ans[2005]; pair <ld, array <int, 2> > dst[2005]; int main() { //freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout); ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; for (int i = 0; i < n; i++) ans[i] = 1e18; for (int i = 0; i < m; i++) { cin >> A[i] >> B[i] >> T[i] >> C[i]; A[i]--; B[i]--; g[A[i]].pb(i); g[B[i]].pb(i); } ld ca = 1, cb = 0; while (1) { for (int i = 1; i < n; i++) dst[i] = {1e18, {int(1e9), int(1e9)}}; se.insert({0.0, 0}); while (sz(se)) { int v = (*se.begin()).S; se.erase(se.begin()); for (auto i : g[v]) { int nxt = opr(i, v); ld val = dst[v].F + ld(ca) * ld(T[i]) + ld(cb) * ld(C[i]); if (val + E < dst[nxt].F) { se.erase({dst[nxt].F, nxt}); dst[nxt] = {val, {dst[v].S[0] + T[i], dst[v].S[1] + C[i]}}; se.insert({dst[nxt].F, nxt}); } } } ld nw = 0; for (int v = 1; v < n; v++) { if (dst[v].F == 1e18) continue; ans[v] = min(ans[v], ll(dst[v].S[0]) * ll(dst[v].S[1])); for (auto i : g[v]) { int nxt = opr(i, v); array <int, 2> a = dst[nxt].S, b = dst[v].S; b[0] += T[i]; b[1] += C[i]; int difa = b[0] - a[0], difb = b[1] - a[1]; if (difa == difb) continue; ld Z = ld(difb) / ld(difb - difa); if (Z + E < ca && Z - E > nw) nw = Z; } } if (nw + E >= ca) break; ca = nw; cb = 1.0 - ca; } for (int i = 1; i < n; i++) if (ans[i] == 1e18) cout << -1 << '\n'; else cout << ans[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...