이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<vector<pair<int,int>>> arr(N);
for (int i = 0; i < M; i++){
arr[A[i]].push_back({B[i],T[i]});
arr[B[i]].push_back({A[i],T[i]});
}
int ans = 0;
vector<int> dp(N,-1);
function<int(int)> f = [&](int src)->int{
queue<array<int,3>> qu;
qu.push({src,0,-1});
int manode = src;
int mm = 0;
vector<int> gez;
while (qu.size()){
int node = qu.front()[0];
int w = qu.front()[1];
int lnode = qu.front()[2];
qu.pop();
if (w>mm) manode=node,mm=w;
for (auto nex : arr[node]){
if (nex.first==lnode) continue;
qu.push({nex.first,nex.second+w,node});
}
}
qu.push({manode,0,-1});
while (qu.size()){
int node = qu.front()[0];
int w = qu.front()[1];
int lnode = qu.front()[2];
qu.pop();
dp[node]=w;
ans=max(ans,w);
if (dp[node]>dp[manode]) manode=node;
for (auto nex : arr[node]){
if (nex.first==lnode) continue;
qu.push({nex.first,nex.second+w,node});
}
}
int ret = dp[manode];
qu.push({manode,0,-1});
while (qu.size()){
int node = qu.front()[0];
int w = qu.front()[1];
int lnode = qu.front()[2];
qu.pop();
ret=min(ret,max(dp[node],w));
for (auto &nex : arr[node]){
if (nex.first==lnode) continue;
qu.push({nex.first,nex.second+w,node});
}
}
return ret;
};
vector<int> ansarr;
for (int i = 0; i < N; ++i)
{
if (dp[i]==-1) {
ansarr.push_back(f(i));
}
}
if (ansarr.size()==1) return ans;
sort(ansarr.begin(), ansarr.end());
for (int i = 0; i < ansarr.size()-1; i++){
ansarr[i]+=L;
}
sort(ansarr.begin(), ansarr.end());
return max(ans,ansarr[ansarr.size()-1]+ansarr[ansarr.size()-2]);
}
컴파일 시 표준 에러 (stderr) 메시지
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int i = 0; i < ansarr.size()-1; i++){
| ~~^~~~~~~~~~~~~~~~~
# | 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... |