백준 소스코드 [C++] 11657 타임머신

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

11657번: 타임머신

백준 소스코드 [C++] 11657 타임머신

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
typedef long long ll;
using namespace std;
int V, E,v,e,weight;
vector <pair<int, int> >adj[500];//V개의 노드에 연결될 간선
vector <ll> bellman(int src) {
	vector <ll> srctodesti(V, 987654321);//src노드에서 각 노드로의 최소비용
	srctodesti[src] = 0;//시작점에서 시작점으로의 거리
	bool check = false;//완화에 성공했는지 여부
	for (int iter = 0;iter < V;iter++) { //(v-1)+1 번 검사.. 마지막검사가 음수 사이클을 판별할 것
		check = false;//완화에 성공한다면 true로 바뀜
		for (int here = 0;here < V;here++) {//V개 노드를 순차적으로 검사
			if (srctodesti[here] == 987654321) continue; //시작점과 연결되지않은 노드라면 넘어감
			for (int num = 0;num < (int)adj[here].size();num++) {//해당노드의 모든 간선을 검사
				int there = adj[here][num].first;
				int cost = adj[here][num].second; 
				if (srctodesti[there] > srctodesti[here] + cost) {//더 작은 비용의 경로가 있다면
					srctodesti[there] = srctodesti[here] + cost; // 그 경로로 바꿔줌
					check = true;//완화성공
				}
			}
		}
		if (check == false) break; //완화실패 = 각 노드에 접근하는 최소비용을 이미 찾음
	}
	if (check == true)  srctodesti.clear();//v번째 검사에 완화가 성공했다면 음수사이클 존재확정
	return srctodesti;//음수사이클이 있다면 빈벡터가 반환되고, 없다면 각 도착지 별 최소비용이 저장된 벡터가 반환됨
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> V >> E;
	for (int i = 0;i < E;i++) {
		cin >> v >> e >> weight;
		adj[v-1].push_back({ e-1,weight });
	}
	vector <ll> res=bellman(0);
	if (res.empty() == true) cout << "-1";//음수 사이클의 존재
	else {
		for (int i = 1;i < V;i++) {
			if ( res[i]==987654321) cout << "-1" << '\n';//경로가 존재하지 않을 때
			else cout << res[i] << '\n';
		}
	}
	return 0;
}