oj.uz

Submission #237742

# Submission time Handle Problem Language Result Execution time Memory
237742 2020-06-08T14:46:48 Z VEGAnn Ceste (COCI17_ceste) C++14
0 / 160
 2500 ms 640 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 = 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 < 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;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2565 ms 384 KB Time limit exceeded

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2585 ms 384 KB Time limit exceeded

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2578 ms 384 KB Time limit exceeded

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2582 ms 384 KB Time limit exceeded

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2572 ms 640 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2580 ms 512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2577 ms 640 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2574 ms 512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2571 ms 512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2573 ms 640 KB Time limit exceeded
2 Halted 0 ms 0 KB -