1602 - 도망자 원숭이

//1602 - 도망자 원숭이
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
#define INF 200000000
 
int N, M, C;
vector<vector<int>> adj;
vector<pair<int, int>> ptime;
vector<vector<int>> W;
 
void init()
{
    cin >> N >> M >> C;
    W = adj = vector<vector<int>>(N + 1, vector<int>(N + 1, INF));
    ptime = vector<pair<int, int>>(N);
    int x, y, r;
    for (int i = 0; i < N; ++i)
    {
        cin >> ptime[i].first;
        ptime[i].second = i + 1;
    }
    for (int i = 0; i < M; ++i)
    {
        cin >> x >> y >> r;
        adj[x][y] = adj[y][x] = r;
    }
    for(int i = 1; i<=N; ++i)
        adj[i][i] = 0;
    sort(ptime.begin(), ptime.end());
    for (int t = 0; t < N; ++t)
    {
        int k = ptime[t].second;
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= N; ++j)
            {
                if(k == i || k == j)
                    W[i][j] = adj[i][k] + adj[k][j] + ptime[t].first;
                else
                {
                    adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
                    W[i][j] = min(W[i][j], adj[i][k] + adj[k][j] + ptime[t].first);
                }
            }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    init();
    int x, y;
    for (int tn = 0; tn < C; ++tn)
    {
        cin >> x >> y;
        if(W[x][y] >= INF)
            cout << -1 << "\n";
        else
            cout << W[x][y] << "\n";
    }
}

 

 

 

 

 

 

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

1602번: 도망자 원숭이

 

 

 

 

 

 

도망자 원숭이

개는 경로의 정점중 가장 가중치가 큰 정점에 있습니다.

즉 S -> T로 가는 경로는 개가 있는 정점과 가중치가 같거나 작은 정점들로만 이루어져 있습니다.(시작점, 끝점 제외)

정점을 가중치의 오름차순으로 정렬하고 경유점으로 순서대로 플로이드 와샬 알고리즘을 사용하면, 모든 S -> T의 경로중 가장 가중치가 큰 정점에 개가 있는 모든 경로에 대해 구할 수 있습니다.

시작점과 끝점이 경유점인 경우는 W[i][j]를 바로 갱신 시킵니다.

(시작점과 끝점이 경유점이면 기존 경로가 바뀌지 않고, 또 정점은 가중치 오름차순 순으로 등장하기 때문에 W[i][j] 보다 adj[i][k] + adj[k][j] + weight[k]가 크더라도 갱신하는것이 타당합니다.)