#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<int, int> > graph[100000];
ll dist1s[100000];
bool visited[100000];
ll distMatrix[5000][5000];
void DFS(int node) {
visited[node] = true;
for (auto i : graph[node])
{
if (!visited[i.first])
{
dist1s[i.first] = i.second + dist1s[node];
DFS(i.first);
}
}
}
ll find_shortcut(int n, vector<int> l, vector<int> d, int c) {
cout << "Starting\n";
for (int i = 0; i < l.size(); i++)
{
graph[i].push_back({i+1, l[i]});
graph[i+1].push_back({i, l[i]});
}
for (int i = 0; i < d.size(); i++)
{
if (d[i] > 0)
{
graph[i].push_back({i+n, d[i]});
graph[i+n].push_back({i, d[i]});
}
}
cout << "Starting first DFS\n";
DFS(0);
cout << "Done with first DFS\n";
ll maxDist = 0;
int maxVert = -1;
for (int i = 0; i < 2 * n; i++)
{
if (maxDist < dist1s[i])
{
maxDist = dist1s[i];
maxVert = i;
}
dist1s[i] = 0;
visited[i] = false;
}
DFS(maxVert);
ll maxDist2 = 0;
int maxVert2 = -1;
for (int i = 0; i < 2 * n; i++)
{
if (maxDist2 < dist1s[i])
{
maxDist2 = dist1s[i];
maxVert2 = i;
}
dist1s[i] = 0;
}
if (maxVert >= n)
{
maxVert -= n;
}
if (maxVert2 >= n)
{
maxVert2 -= n;
}
graph[maxVert].push_back({maxVert2, c});
graph[maxVert2].push_back({maxVert, c});
cout << "Edge between " << maxVert << " and " << maxVert2 << "\n";
priority_queue<pair<ll, ll> > q;
for (int i = 0; i < 5000; i++)
{
for (int j = 0; j < 5000; j++)
{
distMatrix[i][j] = 1000000000000000000;
}
}
for (int i = 0; i < 2 * n; i++)
{
q.push({0, i});
for (int j = 0; j < 2 * n; j++)
{
visited[j] = false;
}
distMatrix[i][i] = 0;
while (!q.empty())
{
int dist = -q.top().first;
int node = q.top().second;
q.pop();
if (visited[node])
{
continue;
}
visited[node] = true;
for (auto j : graph[node])
{
if (!visited[j.first])
{
distMatrix[i][j.first] = min(distMatrix[i][j.first], distMatrix[i][node] + j.second);
//cout << "Updating distMatrix " << i << j.first << " to " << min(distMatrix[i][j.first], distMatrix[i][node] + j.second) << "\n";
q.push({-distMatrix[i][j.first], j.first});
}
}
}
}
ll toRet = 0;
for (int i = 0; i < 2 * n; i++)
{
for (int j = 0; j < 2 * n; j++)
{
if (distMatrix[i][j] < 1000000000000000000)
{
toRet = max(toRet, distMatrix[i][j]);
}
}
}
return toRet;
}
Compilation message
shortcut.cpp: In function 'll find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:24:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < l.size(); i++)
~~^~~~~~~~~~
shortcut.cpp:29:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < d.size(); i++)
~~^~~~~~~~~~
shortcut.cpp:96:17: warning: unused variable 'dist' [-Wunused-variable]
int dist = -q.top().first;
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
94 ms |
198392 KB |
Secret is incorrect! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
94 ms |
198392 KB |
Secret is incorrect! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
94 ms |
198392 KB |
Secret is incorrect! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
94 ms |
198392 KB |
Secret is incorrect! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
94 ms |
198392 KB |
Secret is incorrect! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
94 ms |
198392 KB |
Secret is incorrect! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
94 ms |
198392 KB |
Secret is incorrect! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
94 ms |
198392 KB |
Secret is incorrect! |
| 2 |
Halted |
0 ms |
0 KB |
- |
