글 읽기 - 시간초과 오류가 나는데 잘 모르겠습니다 ㅠㅠ

bsdlcksdn 8년 전 0

다익스트라? 알고리즘을 제대로 배운적이없어서 대략적으로 짜봤습니다...

재귀? 같이 풀어서

1.시작지점에서 -> 목표지점까지

2.목표지점에서->시작지점까지

두가지로 나눴구요 , 경로를 진행할때마다 최종도달했던 값보다 커지게되면 retrun 시켜서 정지하게끔 했습니다.

제가 다익스트라를 잘 몰라서... 제가 짠 코드대로하면 n,m의 범위가 가능한지 잘 모르겠습니다.;

그리고 빅오를 계산하는법도 잘 몰라서 그런데 혹시 개념적으로 잘 알려주는 사이트 아시면 공유 부탁드리겠습니다~

#include <iostream>
using namespace std;

int n, m, x;
int a, b, t;
int board[1010][1010];
int copy_board[1010][1010];
int result[1010];
int max_count = 99999999;
int temp;

void dijkstra(int data, int count, bool check, int start) {

	//시작->목표
	if (check == false) {

		for (int i = 1; i <= n; i++) {

			if (count + board[data][i] >= max_count)
				return;

			if (i == x && board[data][i] != 0) {
				temp = board[data][i];
				board[data][i] = 0;
				//cout << "aaa : " << data << " " << i << " " << count + temp << endl;
				dijkstra(i, count + temp, true, start);
				board[data][i] = temp;
			}

			else if (board[data][i] != 0) {
				temp = board[data][i];
				board[data][i] = 0;
				//cout << "bbb : " << data << " " << i << " " << count + temp << endl;
				dijkstra(i, count + temp, false, start);
				board[data][i] = temp;
			}
		}

	}

	//목표->시작
	else if (check == true) {

		for (int i = 1; i <= n; i++) {

			if (i == start && board[data][i] != 0 && max_count > count + board[data][i]) {
				//cout << "ccc : " << data << " " << i << " " << count + board[data][i] << endl;
				max_count = count + board[data][i];
			}


			else if (board[data][i] != 0) {
				temp = board[data][i];
				board[data][i] = 0;
				//cout << "ddd : " << data << " " << i << " " << count + temp << endl;
				dijkstra(i, count + temp, true, start);
				board[data][i] = temp;
			}

		}

	}

}


int main() {

	//입력
	cin >> n >> m >> x;

	for (int i = 0; i < m; i++) {
		cin >> a >> b >> t;
		board[a][b] = copy_board[a][b] = t;
	}

	//탐색
	for (int i = 1; i <= n; i++) {

		if (i == x) {
			result[i] = 0;
			continue;
		}

		dijkstra(i, 0, 0, i);

		//초기화
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= n; j++) {
				board[i][j] = copy_board[i][j];
			}
		}

		result[i] = max_count;
		max_count = 99999999;
	}

	int min_count = 0;
	for (int i = 1; i <= n; i++) {
		//cout << result[i] << endl;
		if (result[i] > min_count)
			min_count = result[i];
	}

	cout << min_count << endl;
}

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

문제

문제

출처

ICPC

시간초과 오류가 나는데 잘 모르겠습니다 ㅠㅠ

bsdlcksdn 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말