1005번

1005번 - ACM Craft

다익스트라 알고리즘을 이용해서 문제를 풀 수 있었다. 위상정렬을 이용해서도 풀 수 있을 것 같다. 

(위상정렬 기억이 흐릿해서 인지 다익스트라가 끌렸다. -> 위상정렬 다시 공부)

결국 맨마지막 목적지에서 다른 목적지까지 거리를 모두 구하고, 그 거리의 최대값을 출력하면 된다(단, 가지 못하는 곳 제외)

만약 건물 X->Y라고 한다면 나는 간선을 Y->X로 주었다. 그리고 주어진 시간 값들을 우선 음수로 변경해서, 

다익스트라 알고리즘을 사용했다. 그렇게 되면 최단 거리를 구하는 다익스트라 알고리즘에서 최대값을 구할 수 있게 된다.

최대값을 구하는 이유는 시간은 결국 큰 값에 의해서 좌우되기 때문이다.

<정답 코드>

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int N, K, W, s;
const int INF = 987654321;
int time[1001];
int dist[1001];
void init()
{
    for (int i = 0; i < 1001; i++)
    {
        time[i] = 0;
        dist[i] = INF;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        cin >> N >> K;
        vector<vector<int>> v(N+1);
        init();
        for (int i = 1; i <= N; i++)
        {
            cin >> time[i];
            time[i] = -time[i];
        }
        for (int i = 0; i < K; i++)
        {
            int from, to;
            cin >> from >> to;
            v[to].push_back(from);
        }
 
        cin >> s;
 
        priority_queue<pair<int,int>> q;
        dist[s] = time[s];
        q.push({ -dist[s],s });
 
        while (!q.empty())
        {
            int cost = -q.top().first;
            int here = q.top().second;
            q.pop();
 
            if (dist[here] < cost)
            {
                continue;
            }
 
            for (int i = 0; i < v[here].size(); i++)
            {
                int there = v[here][i];
                int w = time[there];
 
                if (cost + w < dist[there] && dist[here]!=INF)
                {
                    dist[there] = dist[here] + w;
                    q.push({ -dist[there],there });
                }
            }
        }
 
        int ans = -1;
        for (int i = 1; i <= N; i++)
        {
            if (dist[i] != INF && -dist[i] > ans)
            {
                ans = -dist[i];
            }
        }
 
        cout << ans << "\n";
 
 
 
    
    }
 
    return 0;
}