#include<bits/stdc++.h>
using namespace std;
const int N = 2005;
const long long INF = 1e18;
const double eps = 1e-9;
int n, m;
bool used[N];
int p[N], pt[N], pc[N];
double d[N];
long long ans = 9e18, ans1, ans2;
vector < pair < int, int > > anss;
vector < pair < int, pair < int, int > > > g[N];
vector < pair < pair < int, int >, pair < int, int > > > e, cur_e;
inline void build(double x){
for(int i = 1; i <= n; i++){
d[i] = INF;
p[i] = -1;
used[i] = false;
}
d[1] = 0;
set < pair < double, int > > q;
q.insert(make_pair(0, 1));
cur_e.clear();
vector < pair < int, int > > s;
long long cur1 = 0, cur2 = 0;
for(int i = 1; i <= n; i++){
int v = q.begin()->second;
q.erase(q.begin());
used[v] = true;
if(p[v] != -1){
cur_e.push_back(make_pair(make_pair(v, p[v]), make_pair(pt[v], pc[v])));
cur_e.push_back(make_pair(make_pair(p[v], v), make_pair(pt[v], pc[v])));
///cout << "KEK: " << v << " " << p[v] << " " << d[v] << " " << d[p[v]] << " " << pt[v] << " " << pc[v] << "\n";
cur1 += pt[v];
cur2 += pc[v];
s.push_back(make_pair(v, p[v]));
}
for(auto it : g[v]){
int to = it.first,
t = it.second.first,
c = it.second.second;
double val = t * x + c * (1 - x);
if(!used[to] && d[to] > val){
q.erase(make_pair(d[to], to));
d[to] = val;
p[to] = v;
pt[to] = t;
pc[to] = c;
q.insert(make_pair(d[to], to));
}
}
}
///cout << "VALS: " << cur1 << " " << cur2 << "\n";
if(1LL * cur1 * cur2 < ans){
ans = 1LL * cur1 * cur2;
ans1 = cur1;
ans2 = cur2;
anss = s;
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++){
int a, b, c, d;
cin >> a >> b >> c >> d;
a += 1;
b += 1;
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 it1 : cur_e){
for(auto it2 : e){
int t1 = it1.second.first, c1 = it1.second.second,
t2 = it2.second.first, c2 = it2.second.second;
double xx = (c2 - c1) / (double)(t1 - c1 - t2 + c2);
if(x < xx && xx <= new_x){
new_x = xx;
}
}
}
if(x == new_x){
break;
}
x = new_x;
}
cout << ans1 << " " << ans2 << "\n";
for(auto it : anss){
cout << it.first - 1 << " " << it.second - 1 << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
640 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
476 KB |
Output is correct |
| 5 |
Correct |
5 ms |
512 KB |
Output is correct |
| 6 |
Correct |
7 ms |
384 KB |
Output is correct |
| 7 |
Correct |
18 ms |
640 KB |
Output is correct |
| 8 |
Correct |
43 ms |
1404 KB |
Output is correct |
| 9 |
Correct |
3 ms |
384 KB |
Output is correct |
| 10 |
Correct |
4 ms |
512 KB |
Output is correct |
| 11 |
Correct |
7 ms |
384 KB |
Output is correct |
| 12 |
Correct |
107 ms |
504 KB |
Output is correct |
| 13 |
Correct |
135 ms |
384 KB |
Output is correct |
| 14 |
Execution timed out |
2045 ms |
440 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2050 ms |
384 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2060 ms |
640 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2050 ms |
640 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2045 ms |
640 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2020 ms |
1404 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2039 ms |
1532 KB |
Time limit exceeded |
