| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 863747 | Huseyn123 | 꿈 (IOI13_dreaming) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "dreaming.h"
#include <bits/stdc++.h>
#define MAX 100001
#define INF INT_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define gett(x,m) get<m>(x)
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define sorta(a,sz) sort(a,a+sz)
#define inputar(a,b){\
for(int i=0;i<b;i++){\
cin >> a[i];\
}\
}
#define inputvec(a,b){\
for(int i=0;i<b;i++){\
ll num;\
cin >> num;\
a.pb(num);\
}\
}
#define outputar(a,b){\
for(int i=0;i<b;i++){\
cout << a[i] << " ";\
}\
cout << "\n";\
}
#define outputvec(a){\
for(auto x:a){\
cout << x << " ";\
}\
cout << "\n";\
}
#define reset(a,n,v){\
for(int i=0;i<n;i++){\
a[i]=v;\
}\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef double db;
typedef long double ldb;
inline void USACO(string filename){
freopen((filename+".in").c_str(),"r",stdin);
freopen((filename+".out").c_str(),"w",stdout);
}
vector<vector<pii>> g;
vector<int> used;
vector<int> e;
vector<int> dist;
vector<int> pre;
void dfs(int v,int prev){
e.pb(v);
used[v]=1;
for(auto x:g[v]){
if(x.ff==prev){
continue;
}
dist[x.ff]=dist[v]+x.ss;
dfs(x.ff,v);
}
}
void dfs1(int v,int prev){
pre[v]=prev;
for(auto x:g[v]){
if(x.ff==prev){
continue;
}
dist[x.ff]=dist[v]+x.ss;
dfs1(x.ff,v);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
int res;
g.resize(N);
dist.resize(N,0);
used.resize(N,0);
pre.resize(N,0);
for(int i=0;i<M;i++){
g[A[i]].pb(mp(B[i],T[i]));
g[B[i]].pb(mp(A[i],T[i]));
}
int maxd=0;
vector<int> c;
for(int i=0;i<N;i++){
if(used[i]==0){
e.clear();
dfs(i,-1);
int maxd1,ind;
maxd1=-1;
for(auto x:e){
if(dist[x]>maxd1){
maxd1=dist[x];
ind=x;
}
dist[x]=0;
}
dfs1(ind,-1);
maxd1=-1;
int ind1;
for(auto x:e){
if(dist[x]>maxd1){
maxd1=dist[x];
ind1=x;
}
}
maxd=max(maxd,maxd1);
int ind2=ind1;
int h=dist[ind1]-dist[ind];
while(ind1!=ind){
h=min(h,max(dist[ind2]-dist[ind1],dist[ind1]-dist[ind]));
ind1=pre[ind1];
}
c.pb(h);
}
}
sortv(c);
reverse(all(c));
if(c.size()==1){
res=c[0];
}
else{
res=c[0]+c[1]+L;
}
if(c.size()>2){
res=max(res,c[1]+c[2]+2*L);
}
res=max(maxd,res);
return res;
}
int main(){
int n,m,k;
cin >> n >> m >> k;
int A[m],B[m],T[m];
for(int i=0;i<m;i++){
cin >> A[i] >> B[i] >> T[i];
}
cout << travelTime(n,m,k,A,B,T);
}