글 읽기 - 예외 케이스를 알 수 있을까요../.?

bsdlcksdn 7년 전 0

우선 소스를 좀 더럽습니다...

queue와 struct를 연습하려구 쓸모없는 부분이 많이 들어갔구요...

알고리즘은 이분탐색 + BFS를 이용하였습니다.

0~가능한 최고 무게를 이진탐색을 통해 BFS를 돌려가면서 찾는 방식입니다.

예외 케이스를 모르겠네요;;ㅠ

#include <iostream>
#include <queue>

using namespace std;

int n, m;
int map[10010][3];
int visit[10010];
int Start, End;
int max_c=0;

struct Point {

	int x;

};

queue<Point> que;

void init() {

	for (int i = 0; i < n; i++) {
			visit[i] = 0;
	}

	while (!que.empty()) que.pop();

}

void input() {

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		cin >> map[i][0] >> map[i][1] >> map[i][2];

		if (max_c < map[i][2]) {
			max_c = map[i][2];
		}

	}

	cin >> Start >> End;
}

int bfs(int num) {

	init();

	Point now;

	now.x = Start;
	visit[now.x] = 1;
	que.push(now);

	while (!que.empty()) {

		now = que.front();
		que.pop();

		
		//cout << "empty" << endl;

		for (int i = 0; i < m; i++) {
			Point next;
			next.x = map[i][1];

			if (now.x == map[i][0] && visit[next.x] == 0 && map[i][2] >= num) {
				
				//도착
				if (next.x == End) {
					//cout << "END" << endl;
					return 1;
				}
				//다음
				else {
					//cout << "next_x : " << next.x << endl;
					visit[next.x] = 1;
					que.push(next);
				}
			}

			//쌍방향 고려
			next.x = map[i][0];
			if (now.x == map[i][1] && visit[next.x] == 0 && map[i][2] >= num) {

				//도착
				if (next.x == End) {
					//cout << "END" << endl;
					return 1;
				}
				//다음
				else {
					//cout << "next_x : " << next.x << endl;
					visit[next.x] = 1;
					que.push(next);
				}
			}
		}
	}

	return 0;
}

int BS(int low, int high) {

	while (low <= high) {

		int mid = (low + high) / 2;
		//cout << low << " " << mid << " " << high << endl;

		if (bfs(mid)) {
			//cout << "bfs ok" << endl;
			low = mid + 1;
		}
		else {
			//cout << "bfs false " << endl;
			high = mid - 1;
		}
	}

	return high;
}

int main() {

	input();

	cout<<BS(0, max_c);

}

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

문제

문제

출처

ICPC

예외 케이스를 알 수 있을까요../.?

bsdlcksdn 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말