金色2-17182宇宙船

白準宇宙探査船

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

方法

この問題は、惑星間移動の場合、方向が異なり、移動料金も異なり、訪れた場所も再アクセスできるため、通常のMSTでは利用できないということです.そこで,移動経路と現在位置に応じて移動料金を比較し,BFSを用いて最小料金を取得する方式を考える.
ビットマスクとダイナミックプログラミングを用いて実現した.

に答える

まずdp配列を宣言し,通過経路と現在位置を基準に最小移動コストを格納する.
while文は、すでにアクセスしたノードも再アクセスできるため、path値を変更してキューに入れるのは、通知で次のアクセスノードを決定します.
最後に,dpアレイに格納された各ノードの巡回後終了時の移動コストを比較することにより,最低コストを得た.

コード#コード#

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;
int dp[(1<<10)][10];
int route[10][10];

class inform
{
public:
	int path;
	int cur;
	int cost;
};

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

	int N, start;
	cin >> N >> start;
	memset(dp, -1, sizeof(dp));

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
			cin >> route[i][j];
	}

	queue<inform> q;
	dp[(1 << start)][start] = 0;
	inform start_node;
	start_node.cur = start;
	start_node.path = (1 << start);
	start_node.cost = 0;

	q.push(start_node);

	while (!q.empty())
	{
		int cur = q.front().cur;
		int path = q.front().path;
		int cost = q.front().cost;
		q.pop();

		for (int i = 0; i < N; i++)
		{
			int new_path;
			int new_cost = cost;
			int temp = (1 << i);
			if ((path & temp) == temp)
				new_path = path;
			else
				new_path = path ^ (1 << i);

			new_cost += route[cur][i];

			if (dp[new_path][i] == -1 || dp[new_path][i] > new_cost)
			{
				inform in;
				in.cost = new_cost;
				in.path = new_path;
				in.cur = i;
				dp[new_path][i] = new_cost;
				
				q.push(in);
			}
		}
	}

	int Min = -1;

	for (int i = 0; i < N; i++) {
		if (Min == -1 || Min > dp[(1 << N) - 1][i])
			Min = dp[(1 << N) - 1][i];
	}
	cout << Min << endl;

	return 0;
}

もう一つの解法

ビットマスク,動的プログラミングに加えて,Flood−WhallアルゴリズムとDFSを用いて最小費用を求める他の解法も検討した.
これはfloyd−とshallアルゴリズムを用いて各ノードの最小移動距離を求め,DFSを用いて全ノードに最小移動距離でアクセスし,最小コストを出力する方法である.