제출 #79686

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
79686		SamAnd	Cities (BOI16_cities)	C++17	14 / 100	920 ms	73432 KiB

cities

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int N = 100005;
const long long INF = 1000000000000000;
struct ban
{
	int x;
	long long d;
	ban(){}
	ban(int x, long long d)
	{
		this->x = x;
		this->d = d;
	}
};
bool operator<(const ban& a, const ban& b)
{
	return a.d > b.d;
}

int n, k, m;
int b[5];
vector<ban> a[N];

long long d[5][N];

bool c[N];
void djk(int x)
{
	for (int i = 1; i <= n; ++i)
		c[i] = false;
	priority_queue<ban> q;
	q.push(ban(b[x], 0));
	while (1)
	{
		ban t;
		do
		{
			if (q.empty())
				return;
			t = q.top();
			q.pop();
		} while (c[t.x]);
		c[t.x] = true;
		d[x][t.x] = t.d;
		for (int i = 0; i < a[t.x].size(); ++i)
		{
			ban h = a[t.x][i];
			h.d += t.d;
			q.push(h);
		}
	}
}

long long dp[1 << 5][N];
int main()
{
	cin >> n >> k >> m;
	for (int i = 0; i < k; ++i)
		cin >> b[i];
	for (int i = 0; i < m; ++i)
	{
		int x, y, z;
		cin >> x >> y >> z;
		a[x].push_back(ban(y, z));
		a[y].push_back(ban(x, z));
	}
	for (int i = 0; i < k; ++i)
	{
		djk(i);
	}
	for (int x = 0; x < (1 << k); ++x)
	{
		for (int i = 1; i <= n; ++i)
			dp[x][i] = INF;
	}
	for (int i = 0; i < k; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			dp[1 << i][j] = d[i][j];
		}
	}
	for (int x = 0; x < (1 << k); ++x)
	{
		int q = 0;
		for (int j = 0; j < k; ++j)
		{
			if (x & (1 << j))
				++q;
		}
		if (q <= 1)
			continue;
		for (int y = x; y; y = (y - 1) & x)
		{
			int z = x - y;
			if (z == 0)
				continue;
			for (int i = 1; i <= n; ++i)
				dp[x][i] = min(dp[x][i], dp[z][i] + dp[y][i]);
		}
	}
	long long ans = INF;
	for (int i = 1; i <= n; ++i)
	{
		ans = min(ans, dp[(1 << k) - 1][i]);
	}
	cout << ans << endl;
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

cities.cpp: In function 'void djk(int)':
cities.cpp:49:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a[t.x].size(); ++i)
                   ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 22
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26