이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// BEGIN BOILERPLATE CODE
#include <bits/stdc++.h>
using namespace std;
#ifdef KAMIRULEZ
const bool kami_loc = true;
const long long kami_seed = 69420;
#else
const bool kami_loc = false;
const long long kami_seed = chrono::steady_clock::now().time_since_epoch().count();
#endif
const string kami_fi = "kamirulez.inp";
const string kami_fo = "kamirulez.out";
mt19937_64 kami_gen(kami_seed);
long long rand_range(long long rmin, long long rmax) {
uniform_int_distribution<long long> rdist(rmin, rmax);
return rdist(kami_gen);
}
long double rand_real(long double rmin, long double rmax) {
uniform_real_distribution<long double> rdist(rmin, rmax);
return rdist(kami_gen);
}
void file_io(string fi, string fo) {
if (fi != "" && (!kami_loc || fi == kami_fi)) {
freopen(fi.c_str(), "r", stdin);
}
if (fo != "" && (!kami_loc || fo == kami_fo)) {
freopen(fo.c_str(), "w", stdout);
}
}
void set_up() {
if (kami_loc) {
file_io(kami_fi, kami_fo);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
}
void just_do_it();
void just_exec_it() {
if (kami_loc) {
auto pstart = chrono::steady_clock::now();
just_do_it();
auto pend = chrono::steady_clock::now();
long long ptime = chrono::duration_cast<chrono::milliseconds>(pend - pstart).count();
string bar(50, '=');
cout << '\n' << bar << '\n';
cout << "Time: " << ptime << " ms" << '\n';
}
else {
just_do_it();
}
}
int main() {
set_up();
just_exec_it();
return 0;
}
// END BOILERPLATE CODE
// BEGIN MAIN CODE
const int ms = 1e5 + 20;
const int inf = 1e9 + 20;
vector<pair<int, int>> adj[ms];
int ds[ms];
int du[ms];
int dv[ms];
int h[ms];
int g[ms];
bool f[ms];
int n;
void dijk(int d[]) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
for (int i = 1; i <= n; i++) {
if (d[i] == 0) {
h[i] = i;
q.push({0, i});
}
}
while (!q.empty()) {
int cd = q.top().first;
int u = q.top().second;
q.pop();
if (d[u] != cd) {
continue;
}
for (auto x: adj[u]) {
int v = x.first;
if (f[v]) {
continue;
}
int w = x.second;
if (d[u] + w < d[v]) {
d[v] = d[u] + w;
h[v] = h[u];
q.push({d[v], v});
}
}
}
}
bool cmp(int u, int v) {
return dv[u] < dv[v];
}
void just_do_it() {
file_io("4special.inp", "4special.out");
int m, k;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
ds[i] = inf;
du[i] = inf;
dv[i] = inf;
}
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
for (int i = 0; i < k; i++) {
int u;
cin >> u;
g[i] = u;
ds[u] = 0;
}
dijk(ds);
int mi = inf;
int fu = -1;
int fv = -1;
for (int i = 1; i <= n; i++) {
for (auto x: adj[i]) {
int j = x.first;
int w = x.second;
if (h[i] != h[j]) {
if (ds[i] + ds[j] + w < mi) {
mi = ds[i] + ds[j] + w;
fu = h[i];
fv = h[j];
}
}
}
}
du[fu] = 0;
dijk(du);
dv[fv] = 0;
dijk(dv);
sort(g, g + k, cmp);
int res = inf;
for (int i = 0; i < k; i++) {
if (g[i] == fu || g[i] == fv) {
continue;
}
for (int j = 0; j < k; j++) {
if (g[j] != g[i] && g[j] != fu && g[j] != fv) {
res = min(res, mi + du[g[i]] + dv[g[j]]);
break;
}
}
}
for (int i = 1; i <= n; i++) {
ds[i] = inf;
}
for (int i = 0; i < k; i++) {
ds[g[i]] = 0;
}
ds[fu] = inf;
ds[fv] = inf;
f[fu] = true;
f[fv] = true;
dijk(ds);
for (int i = 1; i <= n; i++) {
for (auto x: adj[i]) {
int j = x.first;
int w = x.second;
if (h[i] != h[j]) {
res = min(res, mi + ds[i] + ds[j] + w);
}
}
}
cout << res;
}
// END MAIN CODE
컴파일 시 표준 에러 (stderr) 메시지
RelayMarathon.cpp: In function 'void file_io(std::string, std::string)':
RelayMarathon.cpp:30:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | freopen(fi.c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:33:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | freopen(fo.c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |