#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
typedef long long ll;
mt19937 rng((long long) (new char));
const int N = 100000 + 7;
const int INF = (int) 1e9 + 7;
int n, m, k, best[N];
multiset<int> adj[N];
vector<pair<int, int>> g[N];
queue<int> q;
bool inside[N];
void push(int i, int value) {
if (!inside[i]) {
q.push(i);
inside[i] = 1;
}
for (auto &it : g[i]) {
assert(adj[it.first].find(min(INF, best[i] + it.second)) != adj[it.first].end());
adj[it.first].erase(adj[it.first].find(min(INF, best[i] + it.second)));
}
best[i] = value;
for (auto &it : g[i]) {
/**if (i == 3) {
cout << "aici : " << best[i] << " and " << it.first << ", " << it.second << "\n";
}**/
adj[it.first].insert(min(INF, best[i] + it.second));
}
}
int get_second(int a) {
///cout << " # " << a << "\n";
if ((int) adj[a].size() < 2) {
return INF;
}
auto it = adj[a].begin();
it++;
assert(it != adj[a].end());
return *it;
}
int travel_plan(int nn, int mm, int r[][2], int len[], int kk, int ch[]) {
n = nn;
m = mm;
k = kk;
/// cout << "# " << n << " " << m << " " << k << "\n";
for (int i = 0; i < n; i++) {
g[i].clear();
adj[i].clear();
best[i] = INF;
inside[i] = 0;
}
assert(q.empty());
for (int i = 0; i < m; i++) {
/// cout << r[i][0] << " " << r[i][1] << " and " << len[i] << "\n";
g[r[i][0]].push_back({r[i][1], len[i]});
g[r[i][1]].push_back({r[i][0], len[i]});
adj[r[i][0]].insert(INF);
adj[r[i][1]].insert(INF);
}
///shuffle(ch, ch + k, rng);
for (int i = 0; i < n; i++) {
///shuffle(g[i].begin(), g[i].end(), rng);
}
for (int i = 0; i < k; i++) {
/// cout << i << " : " << ch[i] << "\n";
push(ch[i], 0);
/** if (ch[i] == 2) {
cout << "wtf : " << i << " and " << ch[i] << "\n";
}**/
}
/// cout << "kolrabi\n";
int cnt = 0;
/// cout << " o " << n << " " << m << " " << k << "\n";
while (!q.empty()) {
int a = q.front();
/// cout << a << " -> " << best[a] << "\n";
q.pop();
for (auto &it : g[a]) {
int node = it.first, relax = get_second(node);
if (node == 2 && relax == 0) {
///cout << "what ? " << node << ", " << relax << "\n";
}
if (relax < best[node]) {
push(node, relax);
}
}
}
/**
cout << "print : ";
for (auto &x : adj[2]) {
cout << x << " ";
}
cout << "\n";
exit(0);**/
/// cout << "done\n";
if (best[0] == INF) {
best[0] = -1;
}
return best[0];
}
Compilation message
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:77:7: warning: unused variable 'cnt' [-Wunused-variable]
77 | int cnt = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7372 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
7372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7372 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
7372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7372 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
7372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
