ABC073D.cpp

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

constexpr long long INF = (1LL << 60);

// ワーシャルフロイド法 (1.1 基本実装)
// 負閉路が存在する場合 true を返す
bool FloydWarshall(std::vector<std::vector<long long>>& distances)
{
	const size_t v = distances.size();

	for (size_t i = 0; i < v; ++i)
	{
		for (size_t from = 0; from < v; ++from)
		{
			for (size_t to = 0; to < v; ++to)
			{
				if ((distances[from][i] < INF) && (distances[i][to] < INF))
				{
					distances[from][to] = std::min(distances[from][to], (distances[from][i] + distances[i][to]));
				}
			}
		}
	}

	for (size_t i = 0; i < v; ++i)
	{
		// 負閉路が含まれている場合, distances[i][i] が負になるような i が存在する
		if (distances[i][i] < 0)
		{
			return true;
		}
	}

	return false;
}

int main()
{
	int N, M, R;
	std::cin >> N >> M >> R;

	std::vector<int> vR(R);
	for (auto& r : vR)
	{
		std::cin >> r;
		--r;
	}

	std::vector<std::vector<long long>> distances(N, std::vector<long long>(N, INF));

	for (int i = 0; i < M; ++i)
	{
		int a, b, c;
		std::cin >> a >> b >> c;
		--a; --b;
		distances[a][b] = c;
		distances[b][a] = c;
	}

	for (int i = 0; i < N; ++i)
	{
		distances[i][i] = 0;
	}

	FloydWarshall(distances);

	std::sort(vR.begin(), vR.end());

	long long answer = INF;

	do
	{
		long long sum = 0;

		for (size_t i = 1; i < vR.size(); ++i)
		{
			const int from = vR[i - 1];
			const int to = vR[i];
			sum += distances[from][to];
		}

		answer = std::min(answer, sum);

	} while (std::next_permutation(vR.begin(), vR.end()));

	std::cout << answer << '\n';
}