백준 알고리즘 11657 (타임머신) - C++, Python

[문제] 백준 알고리즘 11657 (타임머신)

> https://www.acmicpc.net/problem/11657

11657번: 타임머신

 

1753 (최단 경로) 문제와 비슷한데, 가중치에 음수(-)도 존재하는 문제이다.

> https://wlstyql.tistory.com/90

백준 알고리즘 1753 (최단경로) - C++, Python

 

최단 경로에서는 다익스트라 알고리즘을 사용했었는데, 비슷하지만

가중치가 음수일 때는 사용이 불가능하므로, 벨만-포드 알고리즘을 쓴다.

 

[문제 해결]

1. graph를 우선순위 힙이 아닌, 일반 배열로 받는다. (일반적 w 누적이랑 다름)

2. 다음 정점 > nw + w가 아닌, 다음 정점 > 이전 정점 + w로 접근한다.

3. 계속 줄어드는지 보기 위해 n번 반복을 한다.

4. 계속 줄어든다면(n번째 까지 값이 갱신된다면), minus=True한다.

5. minus라면 -1, 아니라면 정점의 값을 출력한다. (없으면 -1)

 

[C++]

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

struct DATA {
	int v, nv, w;
};
const int INF = 1e9;
int n, m;
vector<DATA> graph;

void solve_bf(int n, int m) {
	vector<int> bf(n + 1, INF);
	bf[1] = 0;
	bool minus = false;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int v = graph[j].v;
			int nv = graph[j].nv;
			int w = graph[j].w;
			if (bf[v] != INF && bf[nv] > bf[v] + w) {
				bf[nv] = bf[v] + w;
				if (i == n - 1) { // 계속 갱신 중이면
					minus = true;
				}
			}
		}
	}
	if (minus) {
		printf("-1\n");
	}
	else {
		for (int i = 2; i <= n; i++) {
			if (bf[i] != INF) {
				printf("%d\n", bf[i]);
			}
			else {
				printf("-1\n");
			}
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		int v, nv, w;
		scanf("%d %d %d", &v, &nv, &w);
		graph.push_back({ v, nv, w });
	}
	solve_bf(n, m);
	return 0;
}

 

[Python]

import sys
n, m = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]
bf = [1e9] * (n+1)
def solve_bf():
    bf[1] = 0
    minus = False
    for i in range(n):
        for j in range(m):
            v = graph[j][0]
            nv = graph[j][1]
            w = graph[j][2]
            if bf[v] != 1e9 and bf[nv] > bf[v] + w:
                bf[nv] = bf[v] + w
                if i == n-1:
                    minus = True
    if minus:
        print(-1)
    else:
        for i in range(2, n+1):
            if bf[i] == 1e9:
                print(-1)
            else:
                print(bf[i])
solve_bf()