#include<bits/stdc++.h>
using namespace std;
#include "dreaming.h"
int mx1=-1e9,mx2=-1e9,sum,val,n,m,l,u_i,v_i,w_i,d1[100005],d2[100005],u,y,ans=1e9,cost,mx,p[100005],lst,st,md,ed,sup,suck=-1e9,comp=0;
vector<pair<int,int> > v[100005];
vector<int> path,g;
queue<int> q;
void bfs(int x)
{
q.push(x);
d1[x]=0;
mx=-1;
while(!q.empty())
{
u=q.front();
q.pop();
if(d1[u]>mx)
{
mx=d1[u];
x=u;
}
for(int i=0;i<v[u].size();i++)
{
y=v[u][i].first;
cost=v[u][i].second;
if(d1[y]==-1)
{
d1[y]=d1[u]+cost;
q.push(y);
}
}
}
mx=-1;
d2[x]=0;
p[x]=0;
q.push(x);
while(!q.empty())
{
u=q.front();
q.pop();
if(d2[u]>mx)
{
mx=d2[u];
lst=u;
}
for(int i=0;i<v[u].size();i++)
{
y=v[u][i].first;
cost=v[u][i].second;
if(d2[y]==-1)
{
p[y]=u;
d2[y]=d2[u]+cost;
q.push(y);
}
}
}
path.clear();
g.clear();
while(1)
{
if(lst==0)
{
break;
}
path.push_back(lst);
if(p[lst]!=0)
{
g.push_back(d2[lst]-d2[p[lst]]);
}
lst=p[lst];
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n=N;
m=M;
l=L;
for(int i=0;i<m;i++)
{
u_i=A[i]+1;
v_i=B[i]+1;
w_i=T[i];
v[u_i].push_back({v_i,w_i});
v[v_i].push_back({u_i,w_i});
}
memset(d1,-1,sizeof d1);
memset(d2,-1,sizeof d2);
for(int i=1;i<=n;i++)
{
if(d1[i]==-1)
{
++comp;
bfs(i);
/*for(int j=0;j<path.size();j++)
{
printf("%d ",path[j]);
}
printf("\n");
for(int j=0;j<g.size();j++)
{
printf("%d ",g[j]);
}
printf("\n");*/
val=1e9;
for(int j=0;j<g.size();j++)
{
sum+=g[j];
}
suck=max(suck,sum);
sup=0;
val=min(val,max(sup,sum));
for(int j=0;j<g.size();j++)
{
sup+=g[j];
sum-=g[j];
val=min(val,max(sup,sum));
}
if(val>=mx1)
{
mx2=mx1;
mx1=val;
}else if(val>=mx2)
{
mx2=val;
}
}
}
//printf("%d %d\n",mx1,mx2);
if(comp==1)
{
return suck;
}else if(comp==2)
{
return mx1+mx2+l;
}else
{
if(mx2==-1e9)
{
return suck;
}else
{
return max(suck,mx1+mx2+l);
}
}
}
Compilation message
dreaming.cpp: In function 'void bfs(int)':
dreaming.cpp:22:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i=0;i<v[u].size();i++)
| ~^~~~~~~~~~~~
dreaming.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i=0;i<v[u].size();i++)
| ~^~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:105:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int j=0;j<g.size();j++)
| ~^~~~~~~~~
dreaming.cpp:112:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for(int j=0;j<g.size();j++)
| ~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
38 ms |
9776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
3404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
38 ms |
9776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
17 ms |
6428 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
6508 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
3404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
38 ms |
9776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
