글 읽기 - 왜 시간초과가 아니라 틀렸습니다가 뜨는지 잘모르겠습니다..

nohhans 7년 전 0

현재 위치별 모든 노드 탐색해가면서 마지막노드일떄 최소 텔레포트횟수를 출력하는 방식으로 짯는데 왜 틀렸습니다가 뜨는지 잘모르겠네요 ㅜㅜ

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 987654321
int n, t, m, a, vis[22][102][55];// 텔레포트횟수 높이 현재노드 
vector<int> v[102]; // 노드의 나무구멍 저장
queue<pair<int, int> > q;

int main() {
	scanf("%d%d", &n, &t);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &m);
		for (int j = 0; j < m; j++) scanf("%d", &a), v[i].push_back(a);
	}
	int ans = INF;
	q.push({ 0,1 });
	int node = 0;
	while (!q.empty()) {
		for (int iter = 0; iter < q.size(); iter++) {
			int ct = q.front().first;
			int h = q.front().second;
			q.pop();
			if (node == n) {
				ans = min(ans, ct);
				continue;
			}
			
			for (int i = 0; i < v[node+1].size(); i++) {
				if ((v[node + 1][i] == h) || (v[node + 1][i] == h + 1) || (v[node + 1][i] == h - 1) || (v[node + 1][i] == h * 2) || (h > 10 && v[node + 1][i] == 20)) {
					if (vis[v[node + 1][i]][node + 1][ct] != 1) {
						vis[v[node + 1][i]][node + 1][ct] = 1;
						q.push({ ct, v[node + 1][i] });
					}
				}
				else if(vis[v[node + 1][i]][node + 1][ct + 1] != 1) {
					vis[v[node + 1][i]][node + 1][ct + 1] = 1;
					q.push({(ct + 1), v[node + 1][i]});
				}
			}
		}
		node++;
	}
	if(ans > t) printf("-1");
	else printf("%d", ans);

	return 0;
}

chogahui05 7년 전 0

텔레포트를 할 때와, 그렇지 않을 때 가중치가 다르지 않을까요?

반례 케이스 드릴게요.

가중치가 다른 경우, 무작정 bfs를 적용하면 곤란합니다.

nohhans 7년 전 0

감사합니다!!

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

문제

문제

출처

ICPC

왜 시간초과가 아니라 틀렸습니다가 뜨는지 잘모르겠습니다..

nohhans 7년 전 0

chogahui05 7년 전 0

nohhans 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말