| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1141712 | otesunki | 시간이 돈 (balkan11_timeismoney) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <tuple>
int N, M;
std::vector<std::tuple<int, int>> chosen;
std::vector<std::tuple<int, int, int, int>> edges;
std::vector<int> reduction;
/*
template<class ForwardIt, class UnaryPred>
ForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPred p) {
for (ForwardIt i = first; ++i != last;)
if (!p(*i))
*first++ = std::move(*i);
return first;
}
*/
template<class InputIt, class UnaryPred>
constexpr InputIt find_if(InputIt first, InputIt last, UnaryPred p) {
for (; first != last; ++first)
if (p(*first))
return first;
return last;
}
template<class ForwardIt, class UnaryPred>
ForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPred p) {
first = find_if(first, last, p);
if (first != last)
for (ForwardIt i = first; ++i != last;)
if (!p(*i))
*first++ = std::move(*i);
return first;
}
int main(void) {
std::cin >> N >> M;
reduction.resize(N);
for (int i = 0; i < N; ++i) {
reduction[i] = i;
}
for (int i = 0; i < M; ++i) {
int a, b, t, c;
std::cin >> a >> b >> t >> c;
edges.push_back({a, b, t, c});
}
int time = 0, cost = 0;
for (;;) {
int mintime = -1, mincost = -1, mina = -1, minb = -1;
/*
std::cout << " time=" << time << "\n";
std::cout << " cost=" << cost << "\n";
for (int i = 0; i < edges.size(); ++i) {
std::cout << std::get<0>(edges[i]) << " [" << reduction[std::get<0>(edges[i])] << "] -> "
<< std::get<1>(edges[i]) << " [" << reduction[std::get<1>(edges[i])] << "] (t="
<< std::get<2>(edges[i]) << " | c=" << std::get<3>(edges[i]) << ")\n";
}
*/
for (int i = 0; i < edges.size(); ++i) {
int thistime = (std::get<2>(edges[i]) + time);
int thiscost = (std::get<3>(edges[i]) + cost);
/*
std::cout << "thistime=" << thistime << "\n";
std::cout << "thiscost=" << thiscost << "\n";
std::cout << "mintime=" << mintime << "\n";
std::cout << "mincost=" << mincost << "\n";
*/
if ((thistime * thiscost < mintime * mincost) || (mina == -1)) {
mintime = thistime;
mincost = thiscost;
mina = std::get<0>(edges[i]);
minb = std::get<1>(edges[i]);
}
}
time = mintime;
cost = mincost;
int minredi = 201, maxredi = 0;
chosen.push_back({mina, minb});
int reductionminb = reduction[minb];
int reductionmina = reduction[mina];
/*
std::cout << "merge " << reductionmina << " with " << reductionminb << "\n";
*/
for (int i = 0; i < N; ++i) {
if (reduction[i] == reductionminb) {
reduction[i] = reductionmina;
}
if (reduction[i] < minredi) {
minredi = reduction[i];
}
if (reduction[i] > maxredi) {
maxredi = reduction[i];
}
}
if (minredi == maxredi) {
break;
}
auto it = remove_if(std::begin(edges), std::end(edges), [](auto edge) {
/*
std::cout << " compare " << reduction[std::get<0>(edge)] << " & " << reduction[std::get<1>(edge)] << "\n";
*/
return reduction[std::get<0>(edge)] == reduction[std::get<1>(edge)];
});
edges.erase(it, std::end(edges));
}
std::cout << time << " " << cost << "\n";
for (auto edge : chosen) {
std::cout << std::get<0>(edge) << " " << std::get<1>(edge) << "\n";
}
return 0;
}