제 생각엔 코드 전체를 봐야 분석이 가능할것같습니다.
위의 소스는 안되고 아래 소스는 돼요.
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
#include <cstring>
using namespace std;
vector < vector < pair < int , int > > > v;
bool visit[100004];
int cnt[100004];
int Max=0;
int vertex=0;
void bfs(int V){
memset(cnt,0,sizeof(cnt));
memset(visit,false,sizeof(visit));
queue < int > que;
que.push(V);
visit[V]=true;
while(!que.empty()){
int x=que.front();
que.pop();
for(int i=0; i<(int)v[x].size();i++){
if(visit[v[x][i].first]!=true){
cnt[v[x][i].first]=(cnt[x]+v[x][i].second);
que.push(v[x][i].first);
visit[v[x][i].first]=true;
if(Max<cnt[v[x][i].first]){
vertex=v[x][i].first;
Max=cnt[v[x][i].first];
}
}
}
}
}
int main(){
int n;
scanf("%d",&n);
for(int i=0; i<n; i++){
int V;
int a,length;
scanf("%d",&V);
v.resize(V+1);
while(1){
scanf("%d",&a);
if(a==-1){
break;
}
scanf("%d",&length);
v[V].push_back(make_pair(a,length));
}
}
bfs(1);
Max=0;
bfs(vertex);
printf("%d\n",Max);
}
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
#include <cstring>
using namespace std;
vector < pair < int , int > > v[100004];
bool visit[100004];
int cnt[100004];
int Max=0;
int vertex=0;
void bfs(int V){
memset(cnt,0,sizeof(cnt));
memset(visit,false,sizeof(visit));
queue < int > que;
que.push(V);
visit[V]=true;
while(!que.empty()){
int x=que.front();
que.pop();
for(int i=0; i<(int)v[x].size();i++){
if(visit[v[x][i].first]!=true){
cnt[v[x][i].first]=(cnt[x]+v[x][i].second);
que.push(v[x][i].first);
visit[v[x][i].first]=true;
if(Max<cnt[v[x][i].first]){
vertex=v[x][i].first;
Max=cnt[v[x][i].first];
}
}
}
}
}
int main(){
int n;
scanf("%d",&n);
for(int i=0; i<n; i++){
int V;
int a,length;
scanf("%d",&V);
while(1){
scanf("%d",&a);
if(a==-1){
break;
}
scanf("%d",&length);
v[V].push_back(make_pair(a,length));
}
}
bfs(1);
Max=0;
bfs(vertex);
printf("%d\n",Max);
}
트리의 지름 1167 문제입니다.
댓글을 작성하려면 로그인해야 합니다.
resolution15 7년 전
특정한 문제들에서 vector의 정적배열 했을때는 맞았습니다가 나오고
resize로 동적으로 배열하면 시간초과가 납니다. 혹시 둘의 시간차이가 있나요?