This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ft first
#define sd second
#define pii pair<int,int>
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 2010;
const int M = 2010;
const ll OO = 1e18;
const int oo = 2e9;
const ld E = 1e-9;
set<pair<ld, int> > pq;
vector<int> g[N];
int n, m, A[M], B[M], T[M], C[M];
ll ans[N];
pair<ld, pii> dist[N];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> n >> m;
fill(ans, ans + n, OO);
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++)
dist[i] = {OO, {oo, oo}};
pq.insert({0.0, 0});
while (sz(pq) > 0){
int v = (*pq.begin()).sd;
pq.erase(pq.begin());
for (int nm : g[v]){
int u = (A[nm] == v ? B[nm] : A[nm]);
ld nw = dist[v].ft + ld(T[nm]) * ld(ca) + ld(C[nm]) * ld(cb);
if (nw + E < dist[u].ft){
pq.erase({dist[u].ft, u});
dist[u] = {nw, {dist[v].sd.ft + T[nm], dist[v].sd.sd + C[nm]}};
pq.insert({dist[u].ft, u});
}
}
}
ld nw = 1;
for (int i = 0; i < n; i++) {
if (dist[i].sd.sd == oo) continue;
if (i > 0)
ans[i] = min(ans[i], ll(dist[i].sd.ft) * ll(dist[i].sd.sd));
for (int nm : g[i]){
int u = (A[nm] == i ? B[nm] : A[nm]);
// if (dist[u].ft <= dist[i].ft) continue;
pii a = dist[u].sd, b = dist[i].sd;
b.ft += T[nm];
b.sd += C[nm];
ll cA = b.ft - a.ft, cB = b.sd - a.sd;
if (cA == cB) continue;
ld cand = ld(cB) / (ld(cB) - ld(cA));
if (cand < 0) continue;
if (cand < nw)
nw = cand - E;
}
}
if (nw + E >= ca) break;
ca = nw;
cb = 1 - nw;
}
for (int i = 1; i < n; i++)
cout << (ans[i] == OO ? -1 : ans[i]) << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |