This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <random>
#include <time.h>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<ll, ll>
#define f first
#define s second
const int inf = 0x3f3f3f3f;
const int mxn = 2000;
int n, m;
int u[mxn], v[mxn], a[mxn], b[mxn];
pi d[mxn];
set<pi> pq;
vector<int> g[mxn];
pi djk(ll x, ll y, int z){
for(int i = 1; i < n; i++) d[i] = {inf, inf};
pq.clear();
pq.insert({0, 0});
while(!pq.empty()){
int c = pq.begin()->s;
pq.erase(pq.begin());
if(c == z) break;
for(int i : g[c]){
int j = c ^ u[i] ^ v[i];
ll dj = d[j].f * x + d[j].s * y, dc = (d[c].f + a[i]) * x + (d[c].s + b[i]) * y;
if(dj > dc){
pq.erase({dj, j});
d[j] = {d[c].f + a[i], d[c].s + b[i]};
pq.insert({dc, j});
}
}
}
return d[z];
}
ll f(pi x){
return x.f * x.s;
}
pi ff(pi x, pi y){
return f(x) < f(y) ? x : y;
}
pi sol(pi l, pi r, int x){
pi p = djk(r.s - l.s, l.f - r.f, x);
if((p.f - l.f) * (r.s - l.s) == (p.s - l.s) * (r.f - l.f)) return ff(l, r);
if(f(djk(p.f, p.s, x)) < f(djk(p.f + 1, p.s, x))) sol(l, p, x);
else sol(p, r, x);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i = 0; i < m; i++){
cin >> u[i] >> v[i] >> a[i] >> b[i];
g[--u[i]].push_back(i);
g[--v[i]].push_back(i);
}
for(int i = 1; i < n; i++){
pi ret = ff(djk(0, 1, i), djk(1, 0, i));
for(int j = 0; j < 100; j++){
ret = ff(ret, djk(rand() % inf, rand() % inf, i));
}
//pi ret = sol(djk(0, 1, i), djk(1, 0, i), i);
cout << (ret.f != inf ? ret.f * ret.s : -1) << endl;
}
return 0;
}
Compilation message (stderr)
ceste.cpp: In function 'std::pair<long long int, long long int> sol(std::pair<long long int, long long int>, std::pair<long long int, long long int>, int)':
ceste.cpp:57:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |