Submission #237748

#	Time	Username	Problem	Language	Result	Execution time	Memory
237748		VEGAnn	Ceste (COCI17_ceste)	C++14	160 / 160	513 ms	660 KiB

ceste

#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]);

                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 + 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 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16