반응형
문제링크: https://www.acmicpc.net/problem/11657
11657번: 타임머신
첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.
www.acmicpc.net
노드마다 최소비용을 구하는 밸만 포드
접근방식
1. 노드마다 최소비용을 구해야 함으로 다익스트라인가 생각함
2. 음수값이 포함됨으로 밸만포드로 구현하자
문제풀이
1. 전형적인 밸만포드문제. 얍문님 블로그만큼 설명을 잘할 자신이 없어서 링크 첨부
https://yabmoons.tistory.com/365
[ 벨만포드 알고리즘 ] 개념과 구현방법 (C++)
이번 글에서는 벨만포드 알고리즘에 대해서 알아보자. 1. 벨만포드 알고리즘 ?? 그래프 알고리즘에서 '최소비용'을 구하는 대표적인 알고리즘으로는 '다익스트라 알고리즘', '벨만포드 알고리즘'
yabmoons.tistory.com
2. 조심해야할 부분은 dist배열을 long long 자료형을 사용해야 된다는점
정답 코드
#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector<pair<pair<int, int>, int>> vec;
long long dist[501];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int from, to, cost;
cin >> from >> to >> cost;
vec.push_back(make_pair(make_pair(from, to), cost));
}
for (int i = 1; i <= n; i++)
dist[i] = 2000000000;
dist[1] = 0;
for (int i = 1; i <= n - 1; i++) {
for (int j = 0; j < vec.size(); j++) {
int from = vec[j].first.first;
int to = vec[j].first.second;
int cost = vec[j].second;
if (dist[from] == 2000000000) continue;
if (dist[to] > dist[from] + cost) {
dist[to] = dist[from] + cost;
}
}
}
for (int j = 0; j < vec.size(); j++) {
int from = vec[j].first.first;
int to = vec[j].first.second;
int cost = vec[j].second;
if (dist[from] == 2000000000) continue;
if (dist[to] > dist[from] + cost) {
cout << -1 << endl;
return 0;
}
}
for (int i = 2; i <= n; i++) {
if (dist[i] == 2000000000)
cout << -1 << endl;
else
cout << dist[i] << endl;
}
return 0;
}
반응형