|

General

# Author Problem Lang Verdict Time Memory Sent Judged
53560495 Practice:
mnbvmar
1149D - 35 C++17 (GCC 7-32) Accepted 670 ms 47272 KB 2019-04-30 12:12:05 2019-04-30 12:12:05
→ Source
#include <bits/stdc++.h>

using namespace std;

const int MaxN = 80;
const int kCompoSizeBound = 4;

int N, M, A, B;
vector<vector<int>> large_cheap_compos;
bool is_same_compo[MaxN][MaxN];

bool visited[MaxN];
vector<int> cur_component;

void DfsCheap(int v) {
visited[v] = true;
cur_component.push_back(v);
for (int s : adj_cheap[v]) {
if (!visited[s]) {
DfsCheap(s);
}
}
}

void FindCheapComponents() {
fill_n(visited, N + 1, false);

for (int v = 1; v <= N; ++v) {
if (!visited[v]) {
cur_component.clear();
DfsCheap(v);
for (int a : cur_component) for (int b : cur_component) {
is_same_compo[a][b] = true;
}
if ((int)cur_component.size() >= kCompoSizeBound) {
const int compo_idx = (int)large_cheap_compos.size();
large_cheap_compos.push_back(cur_component);
for (int vert : cur_component) {
}
}
}
}
}

int32_t main() {
cin >> N >> M >> A >> B;
for (int i = 0; i < M; ++i) {
int u, v, c;
cin >> u >> v >> c;
if (c == A) {
} else {
}
}

FindCheapComponents();

const int S = large_cheap_compos.size();

using State = pair<int, unsigned>;
using QueueElem = pair<int, State>;

priority_queue<QueueElem, vector<QueueElem>, greater<QueueElem>> que;
que.emplace(0, init_state);

const int kInfty = 1e9;
vector<vector<int>> distances(N + 1, vector<int>(1 << S, kInfty));
vector<vector<bool>> dij_visited(N + 1, vector<bool>(1 << S));

while (!que.empty()) {
auto [cost, state] = que.top();
que.pop();

continue;
}

for (int s_cheap : adj_cheap[vert]) {
const int new_dist = cost + A;
}
}

for (int s_large : adj_expensive[vert]) {
if (is_same_compo[vert][s_large]) { continue; }
const int new_dist = cost + B;
}
}
}

for (int i = 1; i <= N; ++i) {
cout << answers[i] << (i == N ? '\n' : ' ');
}
}


?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?