BOJ-11657 타임머신
본 문제는 시간 C가 음수가 나올 수 있기 때문에, 벨만-포드 알고리즘을 사용해야 한다.
음의 페로가 존재한다면 -1 만 출력하고
1부터 A[i] 까지의 거리를 모두 출력하는데 만일 A[i]가 1의정점과 다른 컴포넌트에 있게되면
무한대의 값을 가지게 된다. 이럴때도 -1을 출력해주면 정답이다.
solution
#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
#define MAXN 100000
using namespace std;
int N, M;
vector<list<pair<int, int> > > G;
void bellman_ford(int pos) {
vector<int> d(N);
bool b;
fill(d.begin(), d.end(), MAXN);
d[pos] = 0;
for (int i = 0; i < N; i++){
b = false;
for (int j = 0; j < G.size();j++){
for (auto jt = G[j].begin(); jt != G[j].end(); jt++){
if (d[j] != MAXN && d[jt->first]>d[j] + jt->second){
d[jt->first]=d[j] + jt->second;
b = true;
}
}
}
}
if (b){
cout << -1 << endl;
}
else{
for (auto it = d.begin() + 1; it != d.end(); it++){
if (*it == MAXN)
cout << -1 << endl;
else
cout << *it << endl;
}
}
}
int main() {
cin >> N >> M;
G.assign(N, list<pair<int, int> >());
for (int i = 0; i < M; i++){
int from;
pair<int, int> p;
cin >> from >> p.first >> p.second;
p.first--;
G[from - 1].push_back(p);
}
bellman_ford(0);
return 0;
}
Copyright (C) 2016 (KimBom) all rights reserved.
Related Posts
BOJ-2252 줄 세우기
BOJ-2252 줄 세우기
https://www.acmicpc.net/problem/2252
본 문제는 단순히 입력을 인접리스트인 그래프로 만든뒤에, 위상정렬한 결과를- BOJ-1865 웜홀
BOJ-1865 웜홀
https://www.acmicpc.net/problem/1865
본래 벨만-포드 알고리즘은 방향그래프에서만 적용가능한 알고리즘이다.
하지만 본
- BOJ-1707 이분그래프
BOJ-1707 이분그래프
아래의 사이트는 이분그래프를 판별하는 문제이다.
https://www.acmicpc.net/problem/1707
본 문제는, DFS 탐색