백준 1738 - 골목길

icpc.me/1738

문제 분석

가는 길마다 돈을 갈취당하거나 주울 수 있다. 갔던 곳을 또 가도 똑같은 일이 일어난다.

 

최적의 경로는 보유금을 최대로 한 채로 콘도에 도착하는 경우이며

 

최적의 경로에 도달할 수 없는 경우가 있다고 한다. 다음을 생각해볼 수 있다.

 

1. 콘도에 못가는 경우 : 당연하게도 경로 자체가 없으면 콘도에 갈 수 없다.

 

2. 가는 길에 돈을 얻는 사이클이 있는 경우: 민승이는 최대 보유금을 위해 돈을 줍느라 최대 보유금은 양의 무한대로 발산하므로 콘도에 영영 도착할 수 없게 된다.

 

이 내용들을 고려하여 금액을 가중치로 바꾸면 음수의 가중치를 처리할 수 있는 알고리즘이 필요하다. 벨만포드/SPFA로 풀어보자.

구현

콘도에 갈 수 없는 경우를 미리 처리해주자 $n \leq 100$ 이므로 플로이드 워셜을 통해 간단히 콘도까지 갈 수 있는지 여부를 처리해주자.

 

그 후 벨만포드/SPFA를 돌린다. 보유금을 최대로 얻는다는 것에 유의하여 구현하자.

 

완화 과정에서 콘도에 갈 수 없는 간선은 배제해준다.

 

갱신이 시행될 때마다 배열에 최적해를 저장해주자.

 

완화가 n번 이상 진행되거나 콘도로 갈 수 있는 경로가 없으면 -1을 출력, 갈 수 있으면 저장한 최적해를 출력해주자.

 

전체코드 - SPFA로 구현했다.

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;

int dist[101];
bool visit[101];
bool reachable[101][101];
bool inque[101];
int update[101];
int backward[101];

bool spfa(graph &al);

int main()
{
    fill(dist, dist + 101, -1e9);
    dist[1] = 0;
    ios::sync_with_stdio(false); cin.tie(0);

    int v, e;
    cin >> v >> e;

    graph adj(v + 1);

    for (int i = 0; i < e; ++i)
    {
        int go, to, fee;
        cin >> go >> to >> fee;
        adj[go].push_back({to, fee});
        reachable[go][to] = true;
    }

    for (int c = 1; c <= v; ++c)
        for (int i = 1; i <= v; ++i)
            for (int j = 1; j <= v; ++j)
                if (reachable[i][c] && reachable[c][j])
                    reachable[i][j] = true;
    
    bool res = spfa(adj);

    if (!res)
    {
        cout << -1;
        return 0;
    }

    vector<int> path;
    int printer = v;

    while (1)
    {
        path.push_back(printer);
        if (printer == 1)
            break;
        printer = backward[printer];
    }

    for (auto t = path.rbegin(); t != path.rend(); ++t)
        cout << *t << ' ';
}

bool spfa(graph &al)
{
    queue<int> q;
    q.push(1);
    inque[1] = true;
    ++update[1];

    int last = al.size() - 1;

    while (q.size())
    {
        auto cur = q.front();
        q.pop();

        inque[cur] = false;
        if (!reachable[cur][last])
            continue;

        for (auto item: al[cur])
        {            
            if (dist[item.first] < dist[cur] + item.second)
            {
                dist[item.first] = dist[cur] + item.second;
                backward[item.first] = cur;

                if (!inque[item.first])
                {
                    ++update[item.first];

                    if (update[item.first] >= last)
                        return false;

                    q.push(item.first);
                    inque[item.first] = true;
                }
            }
        }
    }

    return true;
}