Submission #98115

#	Time	Username	Problem	Language	Result	Execution time	Memory
98115		dalgerok	Ceste (COCI17_ceste)	C++17	160 / 160	370 ms	760 KiB

ceste

#include<bits/stdc++.h>
using namespace std;


const int N = 2005;
const long long INF = 1e18;



int n, m;
int sum_t[N], sum_c[N];

double d[N];
long long ans[N];
vector < pair < int, pair < int, int > > > g[N];
vector < pair < pair < int, int >, pair < int, int > > > e;

inline void build(double x){
    for(int i = 1; i <= n; i++){
        d[i] = INF;
    }
    d[1] = 0;
    set < pair < double, int > > q;
    q.insert(make_pair(0, 1));
    while(!q.empty()){
        int v = q.begin()->second;
        q.erase(q.begin());
        for(auto it : g[v]){
            int to = it.first,
                t = it.second.first,
                c = it.second.second;
            if(d[to] > d[v] + t * x + c * (1 - x)){
                q.erase(make_pair(d[to], to));
                sum_t[to] = sum_t[v] + t;
                sum_c[to] = sum_c[v] + c;
                d[to] = d[v] + t * x + c * (1 - x);
                q.insert(make_pair(d[to], to));
            }
        }
    }
    for(int i = 1; i <= n; i++){
        if(d[i] != INF){
            ans[i] = min(ans[i], 1LL * sum_t[i] * sum_c[i]);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        ans[i] = INF;
    }
    for(int i = 1; i <= m; i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        g[a].push_back(make_pair(b, make_pair(c, d)));
        g[b].push_back(make_pair(a, make_pair(c, d)));
        e.push_back(make_pair(make_pair(a, b), make_pair(c, d)));
        e.push_back(make_pair(make_pair(b, a), make_pair(c, d)));
    }
    double x = 0;
    while(true){
        double new_x = 1;
        build(x);
        for(auto it : e){
            int v = it.first.first, to = it.first.second,
                t = it.second.first, c = it.second.second;
            if(d[v] == INF){
                continue;
            }
            int na = sum_t[v] + t,
                nb = sum_c[v] + c,
                ca = sum_t[to],
                cb = sum_c[to];
            double xx = (cb - nb) / (double)(na - nb - ca + cb);
            if(x < xx && xx <= new_x){
                new_x = xx;
            }
        }
        if(x == new_x){
            break;
        }
        x = new_x;
    }
    for(int i = 2; i <= n; i++){
        if(ans[i] == INF){
            ans[i] = -1;
        }
        cout << ans[i] << "\n";
    }
}

• 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