제출 #384075

#제출 시각아이디문제언어결과실행 시간메모리
384075nguyen31hoang08minh2003Ceste (COCI17_ceste)C++14
64 / 160
2570 ms63724 KiB
#include <bits/stdc++.h> #define fore(i, a, b) for (int i = (a), _b = (b); i < _b; ++i) #define fort(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) #define ford(i, a, b) for (int i = (a), _b = (b); i >= _b; --i) #define fi first #define se second #define pb push_back #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() using namespace std; template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;}; template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;}; typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<vi> vvi; typedef vector<vii> vvii; typedef pair<ii, int> Edge; const int maxN = 2005; const ll inf = 1e9 + 31082003; int n, m; ll dc[maxN][maxN], dt[maxN][maxN], res[maxN]; vector<Edge> adj[maxN]; void Input() { int a, b, c, t; cin >> n >> m; fort(_, 1, m) { cin >> a >> b >> t >> c; adj[a].pb(Edge(ii(t, c), b)); adj[b].pb(Edge(ii(t, c), a)); } } void Dijkstra(const int s, ll d[], function<ll(Edge)> cost) { priority_queue<ii, vii, greater<ii> > pq; int u, v; ll w; fort(i, 1, n) d[i] = inf; d[s] = 0; pq.push(ii(0, s)); while (!pq.empty()) { u = pq.top().se; w = pq.top().fi; pq.pop(); if (d[u] != w) continue; for (const Edge &e : adj[u]) { w = cost(e); v = e.se; if (mini(d[v], d[u] + w)) pq.push(ii(d[v], v)); } } } void dfs(const int u, const int x, const ll wt, const ll wc) { static bool vis[maxN]; mini(res[u], wt * wc); if (u == x || vis[u] || (wt + dt[u][x]) * (wc + dc[u][x]) >= res[x] || dt[u][x] >= inf || dc[u][x] >= inf) return; vis[u] = true; for (const Edge &e : adj[u]) dfs(e.se, x, wt + e.fi.fi, wc + e.fi.se); vis[u] = false; } void Solve() { fort(i, 1, n) { Dijkstra(i, dt[i], [](const Edge &e) -> ll {return e.fi.fi;}); Dijkstra(i, dc[i], [](const Edge &e) -> ll {return e.fi.se;}); res[i] = inf * inf; } fort(i, 2, n) { dfs(1, i, 0, 0); cout << (res[i] < inf ? res[i] : -1) << '\n'; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); Input(); Solve(); 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...