6657 | 2023. 12. 15 17:25:25 | anon | Villanyautó | cpp17 | Hibás válasz 2/60 | 800ms | 5348 KiB |
#include <bits/stdc++.h>
#define MAX_N 100
#define FastIO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) x.begin(), x.end()
typedef long long ll;
using namespace std;
const ll INF = ~(1LL << 63);
ll N, M, K, G[MAX_N + 1][MAX_N + 1];
bool vis[MAX_N + 1];
unordered_map<ll,array<ll,2>> states;
void walk(ll node, ll k, ll cap, ll max_cap) {
if(cap < 0)
return;
auto found = states.find(node);
if(found != states.end() && ((found->second[0] > k && found->second[1] > cap) || (found->second[0] == k && found->second[1] > cap) || (found->second[0] > k && found->second[1] == cap)))
return;
if(found == states.end())
states[node] = { k, cap };
else {
found->second[0] = max(k, found->second[0]);
found->second[1] = max(cap, found->second[1]);
}
vis[node] = true;
if(k > 0)
walk(node, k - 1, max_cap, max_cap);
for(ll i = 1; i <= MAX_N; i++) {
if(G[node][i])
walk(i, k, cap - G[node][i], max_cap);
}
}
int main()
{
FastIO;
ll n1, n2, C;
set<ll> caps;
cin >> N >> M >> K;
for(ll i = 0; i < M; i++) {
cin >> n1 >> n2 >> C;
G[n1][n2] = C;
G[n2][n1] = C;
caps.insert(C);
}
set<ll>::iterator it;
for(it = caps.begin(); it != caps.end(); it++) {
fill(vis + 1, vis + N + 1, false);
states.clear();
walk(1, K, 0, *it);
if(all_of(vis + 1, vis + N + 1, [](auto &a) { return a; })) {
cout << *it << '\n';
break;
}
}
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 2/60 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1832 KiB | |||
2 | Elfogadva | 0/0 | 800ms | 2300 KiB | |||
3 | Hibás válasz | 0/1 | 4ms | 2440 KiB | |||
4 | Hibás válasz | 0/1 | 3ms | 2696 KiB | |||
5 | Hibás válasz | 0/1 | 3ms | 3096 KiB | |||
6 | Hibás válasz | 0/2 | 4ms | 3068 KiB | |||
7 | Hibás válasz | 0/2 | 4ms | 3400 KiB | |||
8 | Hibás válasz | 0/2 | 4ms | 3928 KiB | |||
9 | Hibás válasz | 0/1 | 3ms | 3760 KiB | |||
10 | Hibás válasz | 0/1 | 3ms | 3996 KiB | |||
11 | Hibás válasz | 0/1 | 3ms | 3956 KiB | |||
12 | Hibás válasz | 0/2 | 3ms | 4024 KiB | |||
13 | Hibás válasz | 0/2 | 3ms | 3964 KiB | |||
14 | Hibás válasz | 0/2 | 3ms | 4240 KiB | |||
15 | Hibás válasz | 0/3 | 3ms | 4208 KiB | |||
16 | Hibás válasz | 0/3 | 3ms | 4348 KiB | |||
17 | Hibás válasz | 0/2 | 3ms | 4424 KiB | |||
18 | Hibás válasz | 0/2 | 4ms | 4552 KiB | |||
19 | Hibás válasz | 0/2 | 3ms | 4580 KiB | |||
20 | Hibás válasz | 0/2 | 4ms | 4612 KiB | |||
21 | Elfogadva | 2/2 | 86ms | 4460 KiB | |||
22 | Hibás válasz | 0/2 | 3ms | 4460 KiB | |||
23 | Hibás válasz | 0/3 | 4ms | 4512 KiB | |||
24 | Hibás válasz | 0/3 | 6ms | 4688 KiB | |||
25 | Hibás válasz | 0/3 | 6ms | 4992 KiB | |||
26 | Hibás válasz | 0/3 | 8ms | 5244 KiB | |||
27 | Hibás válasz | 0/3 | 189ms | 5132 KiB | |||
28 | Hibás válasz | 0/3 | 4ms | 4984 KiB | |||
29 | Hibás válasz | 0/3 | 4ms | 5116 KiB | |||
30 | Hibás válasz | 0/3 | 14ms | 5348 KiB |