[백준/BOJ] 백준 1602번 : 도망자 원숭이

www.acmicpc.net/problem/1602

1602번: 도망자 원숭이

멍멍이가 괴롭힐 수 있는 시간이 작은 순으로 정렬하고 그 순서로 플로이드 알고리즘을 이용해 문제를 해결했다. 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <string>
#include <cstdlib>
#include <deque>
#include <set>
using namespace std;

int n, m, q;
vector<pair<int, int>> dog2;
vector<int> dog1(501);
int adj1[501][501];
int adj2[501][501];

void Pre()
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			if (i == j)
			{
				adj1[i][j] = 0;
				adj2[i][j] = 0;
			}
			else
			{
				adj1[i][j] = 987654321;
				adj2[i][j] = 987654321;
			}
		}
}

//플로이드 알고리즘을 이용
void Solve()
{
	for (int k = 0; k < n; k++)
	{
		int dog_index = dog2[k].second;
		int dog_time = dog2[k].first;

		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
			{
				adj1[i][j] = min(adj1[i][j], adj1[i][dog_index] + adj1[dog_index][j]);
				adj2[i][j] = min(adj2[i][j], adj1[i][dog_index] + adj1[dog_index][j] + max(dog_time, max(dog1[i], dog1[j])));
			}
	}
}



int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m >> q;

	for (int i = 1; i <= n; i++)
	{
		int d_time;
		cin >> d_time;

		dog1[i] = d_time;
		dog2.push_back(make_pair(d_time, i));
	}

	sort(dog2.begin(), dog2.end()); //시간이 가장 적게 걸리는것 순으로 정렬

	Pre();
	for (int i = 0; i < m; i++)
	{
		int a, b, d;

		cin >> a >> b >> d;

		adj1[a][b] = d;
		adj1[b][a] = d;
	}

	Solve();

	for (int i = 0; i < q; i++)
	{
		int s, t;
		int result;

		cin >> s >> t;

		result = adj2[s][t];

		if (result == 987654321)
			cout << -1 << "\n";
		else
			cout << result << "\n";
	}

	return 0;
}