11657번

11657번 - 타임 머신

그래프 상에서 최단 거리를 구하는 알고리즘으로 풀면 된다.

단, 가중치에서 음의 가중치가 존재 하기 때문에, bfs 나 다익스트라를 쓰면 안되고 벨만 포드 알고리즘을 사용하였다.

음의 싸이클이 존재하는 경우는 ( iter == n && update == true) 일 때 이므로 체크해주면 된다.

그리고 도달할 수 없는 경우는 INF 로 남아있기 때문에, 이를 if문으로 걸러서 출력하면 된다.

##SPFA 풀이 추가

<정답 코드 - 벨만포드>

#include<iostream>
#include<vector>
 
using namespace std;
const int INF = 987654321;
int n, m;
bool bellman_ford(int s, vector<vector<pair<int, int>>> &v, vector<int> &upper)
{
    for (int iter = 1; iter <= n; iter++)
    {
        bool update = false;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < v[i].size(); j++)
            {
                int next = v[i][j].first;
                int cost = v[i][j].second;
 
                if (upper[i] != INF && upper[next] > upper[i] + cost)
                {
                    update = true;
                    upper[next] = upper[i] + cost;
                }
 
            }
        }
        if (iter == n && update)
        {
            return false;
        }
    }
 
    return true;
 
}
int main()
{
 
    scanf("%d %d", &n, &m);
 
    vector<int> upper(n + 1);
    vector<vector<pair<int, int>>> v(n + 1);
 
    for (int i = 1; i <= n; i++)
    {
        upper[i] = INF;
    }
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        v[a].push_back(make_pair(b, c));
    }
 
    int start = 1;    //시작점
    upper[start] = 0;    //시작점 상한은 0으로 초기화
 
    if (!bellman_ford(start, v, upper))
    {
        printf("-1\n");                //음수 사이클을 이루는 경우
    }
    else
    {
        for (int i = 2; i <= n; i++)
        {
            if (upper[i] != INF)
            {
                printf("%d\n", upper[i]);        //갈 수 있는 경우 최단 거리
            }
            else
            {
                printf("-1\n");            //갈 수 없는 경우
            }
        }
    }
 
 
 
    return 0;
}

<정답 코드 - SPFA>

 

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int INF = 987654321;
int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int,int>>> v(n + 1);
    while (m--)
    {
        int from, to, w;
        cin >> from >> to >> w;
        v[from].push_back({ to,w });
    }
 
    vector<bool> check(n + 1, false);
    vector<int> dist(n + 1,INF);
    vector<int> cycle(n + 1, 0);
    queue<int> q;
    q.push(1);
    dist[1] = 0;
    check[1] = true;
    cycle[1]++;
 
    while (!q.empty())
    {
        int here = q.front();
        q.pop();
        check[here] = false;
 
        for (int j = 0; j < v[here].size(); j++)
        {
            int there = v[here][j].first;
            int cost = v[here][j].second;
            if (dist[there] > dist[here] + cost && dist[here] != INF)
            {
                dist[there] = dist[here] + cost;
 
                if (!check[there])
                {
                    cycle[there]++;
                    if (cycle[there] == n)
                    {
                        cout << "-1\n";
                        return 0;
                    }
 
                    check[there] = true;
                    q.push(there);
                }
            }
        }
    }
 
 
    for (int i = 2; i <= n; i++)
    {
        if (dist[i] == INF)
        {
            cout << "-1\n";
        }
        else
        {
            cout << dist[i] << "\n";
        }
    }
    return 0;
}