글 읽기 - 특정 케이스에서 계속 틀립니다. 그런데 왜 틀린지 모르겠습니다.

dladydwo123 5년 전 0

구현 원리는

각 정점에 방문할 때, 그 정점까지 도달하기 위한 최단거리가 동일한 경우, 도달하기 전까지 거친 정점의 갯수가 작은것으로 넣어주기
최단거리가 갱신될 경우, 도달하기 전까지 거친 정점의 갯수가 작은것으로 넣어주기

이 2가지로 충분하다고 생각했습니다. 혹시 제가 놓친게 있나요?

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
//#pragma warning(disable:4996)
using namespace std;

struct state {
	int prev;
	int num; //현재까지 방문한 거점의 수.
	int t;
};

int N, M;
vector<pair<int, int>> v[101];
queue<struct state> q;
int visit[101], info[101];

int main() {
	//freopen("input.txt", "r", stdin);
	cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		int a, b, c, d, e;
		cin >> a >> b >> c >> d >> e;
		int num = 0;
		if (e > 10)
			num = c + (e - 10) * d;
		else
			num = c;
		v[a].push_back({ b,num });
		v[b].push_back({ a,num });
	}

	struct state s;
	s.prev = 1;
	s.num = 1;
	s.t = 0;
	q.push(s);

	for (int i = 1; i <= N; i++) {
		info[i] = 1e9;
		visit[i] = 1e9;
	}
	info[1] = 0;
	visit[1] = 0;

	for (;;) {
		int size = q.size();
		if (size == 0) break;

		for (int i = 0; i < size; i++) {
			struct state prev = q.front();
			q.pop();

			if (prev.prev == N) 
				continue;
			

			int len = v[prev.prev].size();
			for (int j = 0; j < len; j++) {
				if (visit[v[prev.prev][j].first] == prev.t + v[prev.prev][j].second) {
					//같은데 방문한 수가 더 적은 경우가 있을 수 있다.
					info[v[prev.prev][j].first] = info[v[prev.prev][j].first] < (prev.num +1)?
						info[v[prev.prev][j].first] : (prev.num+1);

					visit[v[prev.prev][j].first] = prev.t + v[prev.prev][j].second;

					struct state next;
					next.prev = v[prev.prev][j].first;
					next.t = prev.t + v[prev.prev][j].second;
					next.num = info[v[prev.prev][j].first];

					q.push(next);
				}
				else if (visit[v[prev.prev][j].first] > prev.t + v[prev.prev][j].second) {
					info[v[prev.prev][j].first] = prev.num + 1;

					visit[v[prev.prev][j].first] = prev.t + v[prev.prev][j].second;

					struct state next;
					next.prev = v[prev.prev][j].first;
					next.t = prev.t + v[prev.prev][j].second;
					next.num = info[v[prev.prev][j].first];

					q.push(next);
				}
			}
		}
	}

	if (visit[N] == 1e9) {
		cout << "It is not a great way.";
		return 0;
	}
	cout << visit[N] << ' ' << info[N];
	return 0;
}

dladydwo123 5년 전 2

설마설마했는데 무방향 그래프가 아니라 방향 그래프였습니다 ㅋㅋ

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

문제

문제

출처

ICPC

특정 케이스에서 계속 틀립니다. 그런데 왜 틀린지 모르겠습니다.

dladydwo123 5년 전 0

dladydwo123 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말