문제
A 도시에서 시작해 B 도시로 도착하는데 C만큼 걸린다 는 정보가 주어질 때
1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하시오
생각
그래프를 사용해서 푸는 문제에는
그래프 순회(Graph Traversal) ex) BFS, DFS
최소 신장 트리(MST, Minimum Spanning Tree) ex) 크루스칼, 프림
최단 경로 탐색(Shortest Path Algorithm) ex) 다익스트라, 벨만 포드, 플로이드
같이 다양하다
이 문제는 한 점에서 시작해서 나머지 도시로 가는 최단거리를 구하는 문제인데
음의 가중치가 있으므로
그리디하게 그때 그때 작은 가중치로 간게 최단 거리이다 라고 푸는 다익스트라로는 풀 수 없다
벨만 포드를 사용해서 문제를 풀어보자~~!~!
벨만 포드 개념
한 정점에서 다른 모든 정점의 최단 경로를 찾는데 쓰이는 알고리즘으로
가능한 모든 경우를 다 체크하자는 아이디어로
음의 가중치가 있어도 사용가능하나
시간 복잡도가 크다 O(EV)
전제 조건은 '최단 경로는 사이클을 포함하지 않는다' 임
어떤 경로로 가는데 굳이 --o-- 이렇게 돌아 갈 필요 없이
그냥 ---- 이렇게 지나간게 최단 거리라고 보는거지
ex)
-8, 4, 6 가중치인 사이클이 있다면
사이클을 돌면 총 가중치가 2, 안 돌면 0이니까
안 돌고 그냥 지나가는게 최단 경로야~~
근데, -1, -4, 3 가중치인 사이클이 있다고 하자!
사이클을 돌면 총 가중치가 -2임..
계속 돌면 돌수록 가중치가 낮아지니까 최단 경로를 구하기 위해 계속 이 사이클을 돌게됌
이렇게 음의 사이클이 있는 경우에는 벨만 포드로 문제를 해결할 수 없음
이럴땐 최단거리가 없다고 하고, 이 문제에서도 이런 경우에는 -1을 출력하라고 한다!!!
쨌든 최단 경로는 사이클을 포함하지 않는다니까
V개의 정점이 있을 때, 같은 정점을 2번 지나지 않게 되고,
이는 최대 V-1개의 간선을 사용해서 최단 경로를 구할 수 있는거임!~!~
벨만 포드 구현
Loop를 V-1번(최악의 경우도 해결하기 위해) 돌리면서
간선을 1개 사용했을 때, 2개, 3개,, V-1개 사용했을 때 최단 경로를 구함
for(int i=0; i<N-1; i++){ //i개의 간선을 거쳤을 때 최단 경로를 구하는 for문
for(int j=0; j<N; j++){ //모든 정점을 보는 for문
for(auto &p: adj[j]){ //한 정점의 연결된 간선을 도는 for문
//최단 경로이면 갱신
}
}
}i-1 번째 루프에서 최대 i-1개 간선을 거치는 최단 경로를 다 구한 후
i번째 루프에서 그 정보들을 사용해서 또 다른 최단경로가 있으면 갱신하는 느낌!!
음의 싸이클 유무
원래 벨만 포드 알고리즘은 위와 같이 N-1 만큼 돌면(==최대 N-1개 간선을 사용)
가능한 모든 경우를 다 본 것이기 때문에 더 이상 Loop를 돌아도 최단거리가 갱신되지 않아야한다
근데 만약 N-1번 이후에 Loop를 돌았을 때
최단 거리가 갱신된다면 음의 싸이클이 존재하는거겠지?
N-1 이상의 간선을 지나 최단 거리가 갱신된 것이니까~!!~!
그래서 i를 (N-1) + 1번 돌려서 음의 싸이클 유무를 알아낼 수 있당
for(int i=0; i<N; i++){ //i개의 간선을 거쳤을 때 최단 경로를 구하는 for문
for(int j=0; j<N; j++){ //모든 정점을 보는 for문
for(auto &p: adj[j]){ //한 정점의 연결된 간선을 도는 for문
//최단 경로이면 갱신
if(i == N-1) 음의싸이클유 = true;
}
}
}출력 초과
완전 처음? 오랜만에? 보는 에러였음
-1 만 나와야하는데 내가 여러개 출력했기 때문에
출력의 개수가 달라서 나오는 에러라고 함
음.. 구현은 잘 했는데.. 뭘까 하고 알아보니까
출력하는 경로 거리를 저장해놓는 result배열을
int가 아니라 long long으로 선언해줘야함
음.. 버스 노선의 개수는 최대 6000개고, 가능한 가중치가 최대 10000이니까
6000 * 10000은 int로 충분히 감당가능한데 어째서일까 했는데
ex)
1 <- 2 -100
1 -> 2 -100
이렇게 서로 서로 연결되어있을때
한번 포문돌면 -100 그다음 포문돌면 -300.. 이렇게 업데이트 되니까
6000 10000 이 아니라 최대 500 6000 * 10000 도 만들어 질 수 있으니까
long long으로 선언해야해
틀렸습니다
모든 그래프는 연결이 안 되어있을 수있으니까
result가 INF인 경우도 -1을 출력해주도록 해야함
반례
3 1
2 3 1
-1
-1
을 출력해야해
코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <utility>
#include <functional>
#define INF 987654321
using namespace std;
int n, m;
int startV;
vector<pair<int, int>> info[505];
long long result[505];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
info[a].push_back(make_pair(b, c));
}
fill(result + 1, result + n + 1, INF);
result[1] = 0;
bool flag = true;
for (int i = 0; i < n; i++) {
for (int j = 1; j <= n; j++) {
if (result[j] != INF) {
for (auto& p : info[j]) {
int nextnode = p.first;
int nextweight = p.second;
if (result[nextnode] > result[j] + nextweight) {
if (i == n - 1) {
flag = false;
break;
}
else {
result[nextnode] = result[j] + nextweight;
}
}
}
}
}
}
if (flag) {
for (int i = 2; i <= n; i++) {
if (result[i] != INF) {
cout << result[i] << "\n";
}
else {
cout << -1 << "\n";
}
}
}
else {
cout << -1 << "\n";
}
return 0;
}