oj.uz

Submission #79686

# Submission time Handle Problem Language Result Execution time Memory
79686 2018-10-15T12:07:12 Z SamAnd Cities (BOI16_cities) C++17
14 / 100
 920 ms 73432 KB 
#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;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2816 KB Output is correct
3 Correct 5 ms 2856 KB Output is correct
4 Incorrect 4 ms 3080 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 26760 KB Output is correct
2 Correct 700 ms 30696 KB Output is correct
3 Correct 237 ms 30696 KB Output is correct
4 Correct 607 ms 40564 KB Output is correct
5 Correct 575 ms 40564 KB Output is correct
6 Correct 445 ms 48148 KB Output is correct
7 Correct 8 ms 48148 KB Output is correct
8 Correct 10 ms 48148 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 48148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 814 ms 55580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 920 ms 73432 KB Output isn't correct
2 Halted 0 ms 0 KB -