[BOJ] 타임머신

[문제]

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

11657번: 타임머신

[풀이]

11657

맞았습니다!!

2396

8

C++14 / 수정

2343

10초 전

 

1) 한 정점에서 모든 정점을 돌면서 최단 경로를 찾으므로 다익스트라 or 벨만-포드 알고리즘을 사용한다. 

하지만 타임머신을 사용해서 과거로 돌아가는 경우에는 음수 가중치가 있으므로 벨만-포드 알고리즘을 사용했다. 

 

2) 벨만 포드 알고리즘은 최단 경로를 구하지는 않는다. 갈 수 있냐 없냐만 판단한다.

 

3) 음수 사이클이 존재하는 경우 시간이 지날수록 값이 작아진다. 이를 이용해서 음수 사이클을 걸러줘야 한다. 

 

4) 최소 가중치는 res[] 배열에 저장하고 음수가 존재하기 때문에 현재 값이 무한대가 아님을 보장받은 후에 음수 사이클을 검사한다. 

무한대가 아님 ==> 이미 한 번 간 경로를 다시 검사하는 거임 

원래 갔던 것보다 값이 작아졌다 ==> 음수 사이클이 존재한다.

 

5) 벨만-포드 알고리즘에 대한 자세한 설명은 구글에 검색하면 많다. 

---

#include <iostream>
#include <vector>
 
#define MAX_N 501
#define MAX_M 6001
#define INF 987654321
using namespace std;
 
//타임머신 (벨만포드 알고리즘 사용 -> 한 정점에서 출발하여 모든 정점으로 가는 최단 경로를 구할 때 음수의 가중치가 있는 경우  )
typedef pair<int, int> pp;
typedef pair<int, pp> ppp;
 
int n, m, res[MAX_N];
//도시의 수, 버스의 수
vector<ppp> edges[MAX_M];
 
int main()
{
    ios_base::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;
 
        edges[i].push_back(ppp(a, pp(b, c))); //벨만포드는 가중치를 기준으로 정렬 필요없음 음수 가중치가 있기 때문에
    }
    //입력
 
    for (int i = 1; i <= n; i++)
    {
        res[i] = INF;
    }
    res[1] = 0; //시작 도시
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            //벨만포드는 최단 경로 판단 x
            //갈 수 있는지 못가는지만 판단이 가능하다.
 
            int start = edges[j].front().first;
            int end = edges[j].front().second.first;
            int cost = edges[j].front().second.second;
 
            //해당 경로로 갈 수 있음 -> 현재 경로가 최소값이다.
            if (res[start] != INF && res[end] > res[start] + cost)
            {
                //res[start] + cost 이 음수가 가능하기 때문에 그냥 대소비교만으로는 안되고
                //지금 값이 무한대가 아님을 보장받은 후에 대소비교를 한다.
                //음수의 변환이 일어남 (음수 사이클 발생 )
                res[end] = res[start] + cost;
            }
        }
    }
 
    bool flag = false;
    //음수 사이클이 발생하면 나옴
 
    for (int j = 0; j < m; j++)
    {
        //음수 사이클은 돌면 돌수록 값이 작아진다.
        //따라서 무한대가 아니면서(이미 한 번 갔던 경로) 원래 값보다 계속 작아지는 경우
        //음수 사이클이 존재한다는 말이기 때문에 음수 사이클을 걸러준다.
 
        int start = edges[j].front().first;
        int end = edges[j].front().second.first;
        int cost = edges[j].front().second.second;
 
        if (res[start] != INF && res[end] > res[start] + cost)
        {
            flag = true; //음수 사이클 존재
            break;
        }
    }
 
    if (flag)
        cout << -1 << '\n';
    else {
        for (int i = 2; i<=n; i++) {
            if (res[i] != INF ) cout << res[i] << '\n';
            else cout << -1 << '\n';
        }
    }
 
    return 0;
}