oj.uz

Submission #237747

# Submission time Handle Problem Language Result Execution time Memory
237747 2020-06-08T14:58:14 Z VEGAnn Ceste (COCI17_ceste) C++14
160 / 160
 528 ms 888 KB 
#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 = 0;

        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 + E < ca && cand - E > nw)
                    nw = cand;
            }
        }

        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;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 580 KB Output is correct
2 Correct 201 ms 512 KB Output is correct
3 Correct 53 ms 512 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 384 KB Output is correct
2 Correct 24 ms 384 KB Output is correct
3 Correct 57 ms 512 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 604 KB Output is correct
2 Correct 246 ms 632 KB Output is correct
3 Correct 394 ms 512 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 556 KB Output is correct
2 Correct 528 ms 740 KB Output is correct
3 Correct 22 ms 512 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 608 KB Output is correct
2 Correct 248 ms 644 KB Output is correct
3 Correct 298 ms 888 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 632 KB Output is correct
2 Correct 292 ms 760 KB Output is correct
3 Correct 292 ms 640 KB Output is correct