글 읽기 - 어디서 틀린건지 모르겠습니다..

cjswo4034 5년 전 0

모든 방향을 구하고 dist[i][k] + dist[k][j] 중 가장 큰 값을 답이라 했을 때는 맞았지만 시간이 오래걸려서

정방향, 역방향 두개로 나눠서 풀어보려 했습니다.

자꾸 틀리다고 나오네요ㅠ

도움 부탁드립니다

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int Max_V = 1000;
const int INF = 1000000000;
typedef pair<int, int> p;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m, x, a, b, c;
	cin >> n >> m >> x;
	vector<p> list[Max_V], reverse[Max_V];
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		list[a - 1].push_back(p(b - 1, c));
		reverse[b - 1].push_back(p(a - 1, c));
	}

	int dist[Max_V], dist_R[Max_V];
	fill(dist, dist + n, INF);
	fill(dist_R, dist_R + n, INF);
	bool visited[Max_V] = {0};
	priority_queue<p, vector<p>, greater<p>> q;

	dist[x - 1] = 0;
	dist_R[x - 1] = 0;
	q.push(p(x - 1, 0));
	while (!q.empty()) {
		int curr = q.top().first;
		q.pop();

		if (visited[curr]) break;

		visited[curr] = true;

		for (int i = 0, leng = list[curr].size(); i < leng; i++) {
			int next = list[curr].at(i).first;
			int weight = list[curr].at(i).second;
			if (dist[next] > dist[curr] + weight) {
				dist[next] = dist[curr] + weight;
				q.push(p(next, dist[next]));
			}
		}
	}
	
	while (!q.empty())
		q.pop();

	fill(visited, visited + n, false);
	q.push(p(x - 1, 0));
	while (!q.empty()) {
		int curr = q.top().first;
		q.pop();

		if (visited[curr]) break;

		visited[curr] = true;

		for (int i = 0, leng = reverse[curr].size(); i < leng; i++) {
			int next = reverse[curr].at(i).first;
			int weight = reverse[curr].at(i).second;
			if (dist_R[next] > dist_R[curr] + weight) {
				dist_R[next] = dist_R[curr] + weight;
				q.push(p(next, dist_R[next]));
			}
		}
	}

	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (dist[i] >= INF || dist_R[i] >= INF) continue;
		ans = max(ans, dist[i] + dist_R[i]);
	}

	cout << ans << endl;

	return 0;
}

rhs0266 5년 전 1

visited[curr]이 true면 break를 하셨는데, 이러면 모든 점까지의 거리를 채 못 구하고 끝나버립니다.

continue를 통해 그 시점의 curr에 대한 작업만 무시해야합니다.

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

문제

문제

출처

ICPC

어디서 틀린건지 모르겠습니다..

cjswo4034 5년 전 0

rhs0266 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말