글 읽기 - 4% 시간초과 질문입니다..

dbstndi6316 3년 전 0

BFS를 이용해서 구현하는데 시간초과가 나서 질문드려요..

뭘 알아봐야될까요

dfs로 해야되나요

#include <iostream>
#include <vector>
#include <queue>
#include<string.h>

using namespace std;

const int MAX = 100001;
vector <pair<int, int>>v[MAX];
int V;
int dist = 0;
int maxdist=0;
int maximum = 0;
bool visited[MAX] = { 0, };

void program(int i) { //bfs 돌려주자
	maxdist = 0;
	queue<pair<int, int>>q;
	q.push({ i, 0 });
	visited[i] = true;
	while (!q.empty()) {
		int x = q.front().first;
		dist = q.front().second;
		q.pop();
		for (int j = 0; j < v[x].size(); j++) {		
			int z = v[x][j].first; // 1과 연결되어있는거
			if (visited[z] == false) {
				int ndist = dist + v[x][j].second;
				visited[z] = true;
				q.push({ z,ndist });
			}
		}
		if (dist > maxdist)
			maxdist = dist;
	}
}

int main() {
	cin >> V;
	for (int i = 0; i < V; i++) {
		int num,n1,n2;
		cin >> num;
		cin >> n1;
		while (n1 != -1) {
			cin >> n2;
			v[num].push_back({ n1,n2 });
			v[n1].push_back({ num,n2 });
			cin >> n1;
		}
	}
	for (int i = 1; i <= V; i++) { //모든 점에서 출발하도록해서 모든점 도착을살핌
		//시간초과
		dist = 0;
		program(i);
		if (maxdist > maximum)
			maximum = maxdist;
		memset(visited,0, sizeof(visited));
	}
	cout << maximum;
	return 0;
}

ahj1592 3년 전 0

51번째 줄이 문제인것같네요

트리의 지름을 구할때 모든 정점에 대해 BFS/DFS를 호출하지 않고 해결할 수 있습니다 (2번이면 됩니다)

dbstndi6316 3년 전 0

네..찾아보니 공식같은게 있더라구요 ?! 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

4% 시간초과 질문입니다..

dbstndi6316 3년 전 0

ahj1592 3년 전 0

dbstndi6316 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말