글 읽기 - 36 퍼센트 정도에서 틀렸다고 나오네요. 도와주세요!

dydsj0920 6년 전 0

임계경로 문제를 풀기 위하여 기본적으로 outdegree 벡터와 와 indegree 배열을 써서 첫번째 답(모든 사람이 만나는데 걸리는 시간)을 구했구요.
2번째 답을 구하기 위하여 from 벡터(사실상 indegree정보를 저장한 벡터)를 통해 도착점->시작점으로 이동하면서 find 함수를 통해 26번줄 처럼 두 간선사이의 weight가 d[now]-d[next]의 값과 같다면 그 길로만 탐색하면서 도로의 개수를 ++ 해주었습니다.

어디서 틀린걸까요?

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAX = 100001;
vector<pair<int, int>> outd[MAX];
vector<pair<int, int>> from[MAX];
int ind[MAX];
int d[MAX];

int find(int n, int m, int s, int e) {

	int ans = 0;

	queue<int> q;
	q.push(e);
	while(!q.empty()){
		int now = q.front();
		q.pop();
		for (int k = 0; k < from[now].size(); k++) {
			int next = from[now][k].first;
			int weight = from[now][k].second;
		
			if (d[now] - d[next] == weight) {
				q.push(next);
				ans++;
			}
		}
	}
	return ans;
}

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);

	for (int i = 0; i < m; i++) {
		int x, y, w;
		scanf("%d %d %d", &x, &y, &w);

		outd[x].push_back(make_pair(y, w));
		from[y].push_back(make_pair(x, w));
		ind[y] += 1;
	}
	int s, e;
	scanf("%d %d", &s, &e);

	//s->e
	queue<int> q;
	q.push(s);
	for (int i = 0; i < n; i++) {
		int now = q.front();
		q.pop();
		for (int k = 0; k < outd[now].size(); k++) {
			int next = outd[now][k].first;
			int weight = outd[now][k].second;

			if (d[next] < d[now] + weight) {
				d[next] = d[now] + weight;
			}

			ind[next] -= 1;
			if (ind[next] == 0) {
				q.push(next);
			}
		}
	}
	printf("%d\n", d[e]);
	printf("%d\n", find(n, m, s, e));

	return 0;
}

ndb796 6년 전 1

결과 구하신 이후에 경로 역추적 하실 때는 한 번 추적이 된 경우는 다시는 추적하지 않도록 해야 합니다.

한 번 추적된 정점에 대해서는 c[정점] = 1; 과 같이 처리하신 뒤에 큐에 담아주세요.

이후에 if(c[정점] = 0) 일 때만 그 정점으로 출발한 정점에 대해서 weight가 d[now]-d[next]와 같은 지 검사하세요. (큐에 담아서)

sorrly 6년 전 1

해결되셨나요>???

ndb796 님이 말씀해주신대로 했는데..

안되요..ㅠㅠ

dydsj0920 6년 전 0

오 예전에 썼던 글인데 해결된걸 깜빡하고 있었네요. 네 ndb796님께서 말씀하신 것처럼 find 함수 안에서 check를 해주고 큐에 Push 해주어야 합니다.

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

문제

문제

출처

ICPC

36 퍼센트 정도에서 틀렸다고 나오네요. 도와주세요!

dydsj0920 6년 전 0

ndb796 6년 전 1

sorrly 6년 전 1

dydsj0920 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말