DRUNKEN

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX_V 500
#define INF 99999

using namespace std;

// first - vertex, second - cost
int adj[MAX_V][MAX_V];
int W[MAX_V][MAX_V];
vector < pair<int, int>> order;
int delay[MAX_V];
int v, e;

void solve();

int main()
{
	cin >> v >> e;

	int delayInput;
	for (int i = 0; i < v; i++)
	{
		cin >> delayInput;

		delay[i] = delayInput;
	}

	for (int i = 0; i < v; i++)
	{
		order.push_back(make_pair(delay[i], i));
	}

	sort(order.begin(), order.end());

	for (int i = 0; i < v; i++)
		for (int j = 0; j < v; j++)
			adj[i][j] = INF;

	int a, b, c;
	for (int i = 0; i < e; i++)
	{
		cin >> a >> b >> c;

		adj[a - 1][b - 1] = c;
		adj[b - 1][a - 1] = c;
	}

	int caseNum;
	cin >> caseNum;

	int s, t;

	solve();

	for (int cIter = 0; cIter < caseNum; cIter++)
	{
		cin >> s >> t;

		cout << "s -> t: " << W[s - 1][t - 1] << endl;
	}
}

void solve()
{
	for (int i = 0; i < v; i++)
	{
		for (int j = 0; j < v; j++)
		{
			W[i][j] = i == j ? 0 : adj[i][j];
		}
	}

	for (int k = 0; k < v; k++)
	{
		for (int i = 0; i < v; i++)
		{
			int w = order[k].second;

			for (int j = 0; j < v; j++)
			{
				adj[i][j] = min(adj[i][j], adj[i][w] + adj[w][j]);
				W[i][j] = min(W[i][j], adj[i][w] + delay[w] + adj[w][j]);
			}
		}
	}
}

DrunkenInput.txt

0.00MB

DrunkenOutput.txt

0.00MB

 

floyd 알고리즘을 구현할 땐 전체 노드의 수만큼 for문을 돈다. 이 문제에서는 k 변수로 나타냈다. 기존 floyd 알고리즘을 응용한 이 문제는, 이 k 변수가 나타내는 값을 단순히 전체 노드를 순회하는 용도에서 한 걸음 더 나아갔다. 바로 가중치가 가장 적은 노드들을 먼저 순회하는 것이다. 그래서 order 라는 변수로 전체 노드를 가중치 순으로 정렬한 후, k번 for문을 돌 때 이 order 변수에 정렬된 노드 순서대로 순회한다. (여기서의 가중치는 간선이 아닌 각 노드가 가지는 값이다.)