//Challenge: Accepted
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define maxn 25005
using namespace std;
struct edge{
int to = 0, t = 0, c = 0;
edge(int x, int z, int w) {
to = x, t = z, c = w;
}
edge();
};
vector<edge> adj[maxn];
vector<pii> hull, slope, ed;
const int inf = 1<<30;
pii mst(int n, int A, int B, bool getans) {
pii ret = make_pair(0, 0);
int mind[n], from[n];
pii save[n];
bool found[n];
for (int i = 0;i < n;i++) mind[i] = inf, found[i] = false, from[i] = -1;
mind[0] = 0;
save[0] = make_pair(0, 0);
for (int cnt = 0;cnt < n;cnt++) {
int mi = inf, ind = 0;
for (int i = 0;i < n;i++) {
if (!found[i] && mind[i] < mi) {
mi = mind[i];
ind = i;
}
}
ret.ff += save[ind].ff, ret.ss += save[ind].ss;
if (getans && from[ind] != -1) ed.push_back(make_pair(ind, from[ind]));
found[ind] = true;
mind[ind] = 0;
for (edge ed:adj[ind]) {
int nv = A * ed.t + B * ed.c;
if (nv < mind[ed.to]) {
mind[ed.to] = nv;
from[ed.to] = ind;
save[ed.to] = make_pair(ed.t, ed.c);
}
}
}
return ret;
}
void solve(int n, pii lef, pii rig) {
//cout << lef.ff << " " << lef.ss << " " << rig.ff << " " << rig.ss << endl;
int xdif = rig.ff - lef.ff, ydif = lef.ss - rig.ss;
pii mid = mst(n, ydif, xdif, false);
if (mid != lef && mid != rig && ydif * mid.ff + xdif * mid.ss < ydif * lef.ff + xdif * lef.ss) {
slope.push_back(make_pair(ydif, xdif));
hull.push_back(mid);
solve(n, lef, mid);
solve(n, mid, rig);
}
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0;i < m;i++) {
int a, b, t, c;
cin >> a >> b >> t >> c;
adj[a].push_back(edge(b, t, c));
adj[b].push_back(edge(a, t, c));
}
pii lef = mst(n, 1, 0, false), rig = mst(n, 0, 1, false);
hull.push_back(lef), hull.push_back(rig);
slope.push_back(make_pair(1, 0)), slope.push_back(make_pair(0, 1));
solve(n, lef, rig);
int ans = inf;
pii out, sl;
for (int i = 0;i < hull.size();i++) {
if (hull[i].ff * hull[i].ss < ans) {
ans = hull[i].ff * hull[i].ss;
out = hull[i];
sl = slope[i];
}
}
cout << out.ff << " " << out.ss << "\n";
mst(n, sl.ff, sl.ss, true);
for (auto i:ed) cout << i.ff << " " << i.ss << "\n";
}
/*
5 7
0 1 161 79
0 2 161 15
0 3 13 153
1 4 142 183
2 4 236 80
3 4 40 241
2 1 65 92
*/
Compilation message
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:82:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int i = 0;i < hull.size();i++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
876 KB |
Output is correct |
| 2 |
Correct |
1 ms |
876 KB |
Output is correct |
| 3 |
Correct |
1 ms |
876 KB |
Output is correct |
| 4 |
Correct |
1 ms |
876 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1004 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 8 |
Correct |
5 ms |
1388 KB |
Output is correct |
| 9 |
Correct |
1 ms |
876 KB |
Output is correct |
| 10 |
Correct |
1 ms |
876 KB |
Output is correct |
| 11 |
Correct |
1 ms |
876 KB |
Output is correct |
| 12 |
Correct |
3 ms |
876 KB |
Output is correct |
| 13 |
Correct |
1 ms |
876 KB |
Output is correct |
| 14 |
Correct |
8 ms |
1004 KB |
Output is correct |
| 15 |
Correct |
18 ms |
1004 KB |
Output is correct |
| 16 |
Correct |
73 ms |
1116 KB |
Output is correct |
| 17 |
Correct |
80 ms |
1132 KB |
Output is correct |
| 18 |
Correct |
72 ms |
1004 KB |
Output is correct |
| 19 |
Correct |
144 ms |
1388 KB |
Output is correct |
| 20 |
Correct |
142 ms |
1536 KB |
Output is correct |
