글 읽기 - cpp 36% 쯤에서 틀리는데 이유를 잘 모르겠습니다ㅜㅜ

jennifer0606 2년 전 0

다익스트라 두번으로 시도해봤고, 파티 지역에서 출발하는 경우도 잘 해결해준 것 같은데 틀렸다고 나오네요ㅠㅠ 반례나 코드 한번 봐주시면 감사하겠습니다..!

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

vector<pair<int, int>> road[1001]; // 도착지, 길이
vector<pair<int, int>> road_back[1001];
int check[1001];
int check_r[1001];

int N, M, X;

void dfs(int n, int s) {
	for (auto a : road[n]) {
		if (n == s) {
			if (check[a.first] == 0 || check[a.first] > a.second) {
				check[a.first] = a.second;
				dfs(a.first, s);
			}
		}
		else if (check[a.first] == 0 || check[a.first] > check[n] + a.second) {
			check[a.first] = check[n] + a.second;
			dfs(a.first, s);
		}
	}
}

void dfs_r(int n, int s) {
	for (auto a : road_back[n]) {
		if (n == s) {
			if (check_r[a.first] == 0 || check_r[a.first] > a.second) {
				check_r[a.first] = a.second;
				dfs_r(a.first, s);
			}
		}
		else if (check_r[a.first] == 0 || check_r[a.first] > check_r[n] + a.second) {
			check_r[a.first] = check_r[n] + a.second;
			dfs_r(a.first, s);
		}
	}
}

int main(int argc, char argv[]) {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> N >> M >> X;

	int s, f, l;
	for (int i = 0; i < M; i++) {
		cin >> s >> f >> l;
		road[s].push_back({ f,l });
		road_back[f].push_back({ s,l });
	}

	int max_time = 0;

	dfs(X,X);
	dfs_r(X,X);
	
	for (int i = 1; i <= N; i++) {
		if (max_time < check[i] + check_r[i])
			max_time = check[i] + check_r[i];
	}

	cout << max_time;
}

jennifer0606 2년 전 1

하이고,,ㅋㅋㅋㅋ 문제를 잘못 이해해서 모든 학생들이 자기마을에서 한번 걸어나갔다가 돌아와야하는줄 알았네요..ㅋㅋㅋ X 마을에 사는 학생이 가야하는 거리를 0으로 바꾸어 주는걸로 해결했습니다..ㅎㅎ

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

문제

문제

출처

ICPC

cpp 36% 쯤에서 틀리는데 이유를 잘 모르겠습니다ㅜㅜ

jennifer0606 2년 전 0

jennifer0606 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말