이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<pair<int, ll>>> adj;
int N;
vector<int> visited;
vector<ll> dist;
ll find_diameter()
{
ll longest = 0;
for (int i = N / 2; i < N; i++)
{
visited = vector<int>(N);
dist = vector<ll>(N, 1ll << 60);
priority_queue<pair<ll, int>> q;
q.push({0, i});
dist[i] = 0;
int cnt = 0;
while (1)
{
int s = q.top().second;
q.pop();
if (visited[s]) continue;
visited[s] = 1; cnt++;
for (auto node : adj[s])
{
if (visited[node.first] || dist[s] + node.second > dist[node.first]) continue;
dist[node.first] = dist[s] + node.second;
q.push({-dist[node.first], node.first});
}
if (cnt == N)
{
longest = max(longest, dist[s]);
break;
}
}
}
return longest;
}
ll find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
N = 2 * n;
adj.resize(N);
for (int i = 0; i < n - 1; i++)
{
adj[i].push_back({i+1, l[i]});
adj[i+1].push_back({i, l[i]});
}
for (int i = 0; i < n; i++)
{
adj[i].push_back({i+n, d[i]});
adj[i+n].push_back({i, d[i]});
}
ll res = 1ll << 60;
for (int i = 0; i < n - 1; i++)
{
for (int j = i+1; j < n; j++)
{
adj[i].push_back({j, c});
adj[j].push_back({i, c});
res = min(res, find_diameter());
adj[i].pop_back();
adj[j].pop_back();
}
}
return res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |