oj.uz

Submission #98115

# Submission time Handle Problem Language Result Execution time Memory
98115 2019-02-20T19:00:33 Z dalgerok Ceste (COCI17_ceste) C++17
160 / 160
 370 ms 760 KB 
#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.0 / 16.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct

Subtask #4
16.0 / 16.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 648 KB Output is correct
2 Correct 125 ms 632 KB Output is correct
3 Correct 34 ms 512 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 512 KB Output is correct
2 Correct 17 ms 512 KB Output is correct
3 Correct 30 ms 640 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 660 KB Output is correct
2 Correct 155 ms 640 KB Output is correct
3 Correct 263 ms 664 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 652 KB Output is correct
2 Correct 370 ms 760 KB Output is correct
3 Correct 17 ms 640 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 732 KB Output is correct
2 Correct 185 ms 640 KB Output is correct
3 Correct 214 ms 704 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 696 KB Output is correct
2 Correct 204 ms 640 KB Output is correct
3 Correct 220 ms 668 KB Output is correct