[Algorithm] Baekjoon 11657번 : 타임머신

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

11657번: 타임머신

 

struct Node
{
    int node;
    long long distance;
};
 
 
vector<vector<Node>> graph(501);
long long dist[501];
int updateCount[501];
bool isInQueue[501];
 
int n, m, a, b, c;
 
bool SPFA(int start)
{
    fill(dist, dist + 501, 1e18);
    isInQueue[start] = true;
    dist[start] = 0;
    updateCount[start] = 1;
 
    queue<Node> q;
    q.push({ start,0 });
 
    while (!q.empty())
    {
        int curNode = q.front().node;
        isInQueue[curNode] = false;
 
        q.pop();
 
        for (int i = 0; i < graph[curNode].size(); ++i)
        {
            int nextNode = graph[curNode][i].node;
            long long nextDistance = graph[curNode][i].distance + dist[curNode];
 
            if (nextDistance < dist[nextNode])
            {
                dist[nextNode] = nextDistance;
                updateCount[nextNode] += 1;
 
                if (!isInQueue[nextNode])
                {
                    if (updateCount[nextNode] >= n)
                    {
                        return false;
                    }
 
                    isInQueue[nextNode] = true;
                    q.push({ nextNode,dist[nextNode] });
                }
            }
        }
    }
 
    return true;
}
 
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
 
    cin >> n >> m;
 
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
        
        graph[a].push_back({ b,c });
    }
 
    if (SPFA(1))
    {
        for (int i = 2; i <= n; ++i)
        {
            if (dist[i] >= 1e18)
            {
                printf("%d\n", -1);
            }
            else
            {
                printf("%lld\n", dist[i]);
            }
        }
    }
    else
    {
        cout << -1;
    }
}

음의 가중치를 갖는 최단거리 문제이다. 

보통 벨만포드 or SPFA를 사용해서 푸는데, 나는 SPFA로 풀었다.

SPFA는 벨만포드를 좀 더 개량한 문제로써, 시간복잡도는 E(간선의 개수)이긴 하지만, 최악의 경우 V+E로 벨만포드와 동일하다고 한다.

 

실제로 이 문제같은경우 벨만포드로 푸는게 더 시간이 잘나오는 경우가 있다고 한다. 

그러나 랜덤케이스의 경우 어지간하면 SPFA가 더 잘 나오며, MCMF라는 알고리즘을 사용할 때도 쓰인다고 하니 앞으로 음의가중치를 갖는 문제의 경우는 SPFA로 풀 것 같다.

코드가 다익스트코드랑 비슷해서 저 습득하기 쉬운것도 있었다.

 

주의해야할 점은 이문제같은경우 3년전? 까지는 dist배열을 int로 했어도 코드가 통과했지만, 2년전쯤 부터는 반드시 long long으로 해야 문제가 통과된다. 저격케이스를 새로 업데이트 했기 때문이다.