#include <bits/stdc++.h>
using namespace std;
const double eps = 0.0001d;
struct edge
{
int x,y,t,c;
};
int n,m;
edge a[10005];
vector<pair<double,pair<int,int>>> e;
map<pair<int,int>,int> timp, cost, idx;
struct sol
{
vector<bool> use;
int v,sumtime,summoney;
};
sol ans;
int tt[205],sz[205];
int rep(int x)
{
while (x != tt[x])
x = tt[x];
return x;
}
void join(int x,int y)
{
x = rep(x);
y = rep(y);
if (x == y)
return;
if (sz[x] < sz[y])
swap(x,y);
sz[x] += sz[y];
tt[y] = x;
}
int main()
{
ans.v = ans.sumtime = 1e9;
ans.summoney = 1;
cin >> n >> m;
ans.use.resize(m + 1);
for (int i = 1; i <= m; i++)
{
cin >> a[i].x >> a[i].y >> a[i].t >> a[i].c;
timp[{a[i].x,a[i].y}] = a[i].t;
cost[{a[i].x,a[i].y}] = a[i].c;
idx[{a[i].x,a[i].y}] = i;
}
vector<double> rate;
for (int i = 1; i <= m; i++)
{
for (int j = i + 1; j <= m; j++)
{
if (a[i].c < a[j].c and a[i].t > a[j].t)
{
double its = (double)(a[j].c - a[i].t) / (double)(a[i].t - a[j].t);
rate.push_back(its - eps);
rate.push_back(its + eps);
}
}
}
for (auto rata : rate)
{
e.clear();
for (int i = 1; i <= m; i++)
{
int x = a[i].x,y = a[i].y;
double cost = (double)a[i].c + rata * (double)a[i].t;
e.push_back({cost,{x,y}});
}
sort(e.begin(),e.end());
for (int i = 0; i < n; i++)
tt[i] = i,sz[i] = 1;
vector<pair<int,int>> luate;
for (auto it : e)
{
if (rep(it.second.first) != rep(it.second.second))
{
luate.push_back(it.second);
join(it.second.first,it.second.second);
}
}
sol cur;
cur.use.resize(m + 1);
cur.summoney = cur.sumtime = 0;
for (auto it : luate)
{
cur.use[idx[it]] = true;
cur.sumtime += timp[it];
cur.summoney += cost[it];
}
cur.v = cur.sumtime + cur.summoney;
if (cur.v < ans.v)
ans = cur;
}
cout << ans.sumtime << ' ' << ans.summoney << '\n';
for (int i = 1; i <= m; i++)
if (ans.use[i])
cout << a[i].x << ' ' << a[i].y << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Incorrect |
5 ms |
848 KB |
Output isn't correct |
| 8 |
Incorrect |
115 ms |
2396 KB |
Output isn't correct |
| 9 |
Correct |
0 ms |
344 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 11 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 12 |
Incorrect |
7 ms |
348 KB |
Output isn't correct |
| 13 |
Correct |
8 ms |
348 KB |
Output is correct |
| 14 |
Incorrect |
1357 ms |
988 KB |
Output isn't correct |
| 15 |
Incorrect |
675 ms |
856 KB |
Output isn't correct |
| 16 |
Execution timed out |
2024 ms |
10440 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2063 ms |
9164 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2072 ms |
10444 KB |
Time limit exceeded |
| 19 |
Runtime error |
73 ms |
65536 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
75 ms |
65536 KB |
Execution killed with signal 9 |
