BOJ 백준온라인져지 1865 웜홀 풀이

다익스트라 알고리즘과 차이점

1. 음수 가중치가 있어도 작동이 된다.

2. 음수 사이클을 체크할 수 있다.

내가 작성한 코드의 worst time complexity 예상 O(V^2*E)

작동방식

1. distance 를 모두 임의의 값으로 체운다.

2. edge 에 가중치들을 넣는다.

3. vertex 만큼 forloop 을 하나 돌린다.

4. 그 안에서 연결된 edge 를 다 체크해준다.

5. cnt 가 N 이 된다는 것은 update 가 된다는 뜻 ( 음수 사이클 )

	#include <cstdio>
	#include <vector>
	/**
	* https://www.acmicpc.net/problem/1865
	* BOJ 백준온라인져지 1865 웜홀 풀이
	*/
	using namespace std;
	int N, M;
	int main () {
	int T;
	scanf("%d", &T);
	while(T--) {
	int N, M, W;
	scanf("%d%d%d", &N, &M, &W);
	int *d = new int[501];
	vector<vector<pair<int, int> > > edges(N + 1);
	for (int i = 0; i < 501; i++) {
	d[i] = 987654321;
	}
	d[1] = 0;
	for (int i = 0; i < M; i++) {
	int S, E, T;
	scanf("%d%d%d", &S, &E, &T);
	edges[S].push_back(make_pair(E, T));
	edges[E].push_back(make_pair(S, T));
	}
	for (int i = 0; i < W; i++) {
	int S, E, T;
	scanf("%d%d%d", &S, &E, &T);
	edges[S].push_back(make_pair(E, -T));
	}
	bool update = true;
	int cnt = 0;
	while (update && cnt != N) {
	cnt++;
	update = false;
	for (int i = 1; i <= N; i++) {
	for (int j = 0; j < edges[i].size(); j++) {
	if (d[edges[i][j].first] > d[i] + edges[i][j].second) {
	d[edges[i][j].first] = d[i] + edges[i][j].second;
	update = true;
	}
	}
	}
	}
	printf("%s\n", cnt == N ? "YES" : "NO");
	}
	}

view raw BOJ_1865.cpp hosted with ❤ by GitHub