백준 알고리즘 1865 (웜홀) - C++, Python

[문제] 백준 알고리즘 1865 (웜홀)

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

1865번: 웜홀

11657 (타임머신)과 거의 같은 벨만-포드 알고리즘 문제이다.

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

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

 

문제 접근 방식은 타임머신과 거의 같다.

웜홀만 (-)가중치를 가진다고 생각하면 된다.

 

 

[문제 해결]

1. graph에 정점과 가중치를 받는다 (웜홀은 (-)가중치)

2. 다음 정점 > 이전 정점 + w로 접근한다.

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

4. 계속 줄어든다면(n번째 까지 값이 갱신된다면), "YES"를 출력한다.

5. 끝까지 진행되었다면 "NO"를 출력한다.

 

[C++]

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

struct SET {
	int v, w;
};
const int MAX = 501;
const int INF = 1e9;
int n, m, w;

void solve_bf(vector<int> bf, vector<SET> graph[MAX]) {
	bf[1] = 0;
	for (int iter = 0; iter < n; iter++) {
		for (int v = 1; v <= n; v++) {
			for (int i = 0; i < graph[v].size(); i++) {
				int nv = graph[v][i].v;
				int nw = graph[v][i].w;
				if (bf[nv] > bf[v] + nw) {
					bf[nv] = bf[v] + nw;
					if (iter == n-1) {
						printf("YES\n");
						return;
					}
				}
			}
		}
	}
	printf("NO\n");
	return;
}

int main() {
	int t;
	scanf("%d", &t);
	for (int i = 0; i < t; i++) {
		scanf("%d %d %d", &n, &m, &w);
		vector<SET> graph[MAX];
		vector<int> bf(n + 1, INF);
		int s, e, t;
		for (int j = 0; j < m; j++) {
			scanf("%d %d %d", &s, &e, &t);
			graph[s].push_back({ e, t });
			graph[e].push_back({ s, t });
		}
		for (int j = 0; j < w; j++) {
			scanf("%d %d %d", &s, &e, &t);
			graph[s].push_back({ e, -t });
		}
		solve_bf(bf, graph);
	}
	return 0;
}

 

[Python]

import sys
T = int(sys.stdin.readline())
def solve_bf(bf, graph, N, M):
    bf[1] = 0
    for it in range(N):
        for v in range(1, N+1):
            for nv, nw in graph[v]:
                if bf[nv] > bf[v] + nw:
                    bf[nv] = bf[v] + nw
                    if it == N-1:
                        print("YES")
                        return
    print("NO")
    return

for _ in range(T):
    N, M, W = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(N+1)]
    bf = [1e9] * (N+1)
    for _ in range(M):
        s, e, t = map(int, sys.stdin.readline().split())
        graph[s].append([e, t])
        graph[e].append([s, t])
    for _ in range(W):
        s, e, t = map(int, sys.stdin.readline().split())
        graph[s].append([e, -t])
    solve_bf(bf, graph, N, M)