글 읽기 - 예외 케이스가 뭐가 있을까요???

jjh4698 8년 전 0

간선간 중복 제거 는 했구요

BFS 돌리는데 마지막점에 도달할경우 W 값을 비교해서 최대값으로 넣어주고

끝에점에 도달했으므로 다른 BFS 탐색이 끝에점에 도달 할 수 있게 CHECK 를 false 로바꾸어 주고,

continue 하게 하였습니다.

예외 케이스가 무엇이있을까요..

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#define INF 1000000001
using namespace std;

int N, M;
bool check[10001];
int dp[10001];
int f1, f2;
vector<vector<pair<int,int> > > v;

queue<pair<int,int > > q;

int has(int x,int y)
{
	for (int i = 0; i < v[x].size(); i++)
	{
		if (v[x][i].first == y)
			return i;
	}
	return -1;
}

int main() {
	int x, y,z,ret=0;
	int temp;
	scanf("%d %d", &N, &M);
	v.resize(N + 1);
	for (int i = 0; i < M; i++)
	{
		scanf("%d %d %d", &x, &y, &z);
		if ((temp=has(x, y))!=-1){
			v[x][temp].second = max(v[x][temp].second, z);
			temp = has(y, x);
			v[y][temp].second = max(v[y][temp].second, z);
		}
		else{
		v[x].push_back(make_pair(y,z));
		v[y].push_back(make_pair(x, z));
		}
	}
	scanf("%d %d", &f1, &f2);
	q.push(make_pair(f1,INF));
	check[f1] = true;

	while (!q.empty())
	{
		int x =q.front().first;
		int w =q.front().second;
		check[x] = true;
		if (x == f2)
		{
			if (ret < w)
				ret = w;
			check[f2] = false; 
			q.pop();
			continue;
		}
		q.pop();

		for (int i = 0; i < v[x].size(); i++)
		{
			if (check[v[x][i].first] == false)
			{
				q.push(make_pair(v[x][i].first, min(w,v[x][i].second)));
			}
		}
	}
	printf("%d", ret);

}

jjh4698 7년 전 0

BFS + 메모이제이션

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

문제

문제

출처

ICPC

예외 케이스가 뭐가 있을까요???

jjh4698 8년 전 0

jjh4698 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말