[백준/c++] 11657 - 타임머신

문제

11657번: 타임머신

풀이

분류 : 벨만-포드 알고리즘

 

최단거리 찾기 + 음의 가중치 이므로 벨만포드 알고리즘을 사용합니다.

 

코드(O((n^2)*m) *O((n^2)*m이 아니라면 알려주세요. 감사합니다(--)(__)*

	#include <iostream>
	#include <vector>
	#include <cstring>
	#define MAX 502
	#define INF 999999999
	using namespace std;
	vector<pair<int, int>> path[MAX];
	int dist[MAX];
	int main() {
	int N, M;
	bool negativeCycle = false;
	cin >> N >> M;
	//도시 초기화(출발도시는 1로)
	for (int i = 2 ; i <= N; i++) dist[i] = INF;
	//경로 초기화
	for (int i = 0; i < M; i++) {
	int start, end, time;
	cin >> start >> end >> time;
	path[start].push_back({end,time});
	}
	for (int i = 1 ; i <= N; i++) {
	for (int j = 1 ; j <= N; j++) {
	vector<pair<int, int>> cur = path[j];
	int size = cur.size();
	for (int k = 0; k < size; k++) {//for(auto &cur : path[j])
	if (dist[j] != INF &&
	dist[cur[k].first] > cur[k].second + dist[j]) {
	dist[cur[k].first] = cur[k].second + dist[j];
	if (i == (N)) negativeCycle = true;
	}
	}
	}
	}
	if (negativeCycle) cout << -1 << '\n';
	else {
	//무한값이 있다면 -1출력, 그외는 저장된 값 출력
	for (int i = 2 ; i <= N; i++) {
	if (dist[i] == INF) cout << -1 << '\n';
	else cout << dist[i] << '\n';
	}
	}
	return 0;
	}

view raw 백준_11657_타임머신.cpp hosted with ❤ by GitHub