Submission #27722

#	Time	Username	Problem	Language	Result	Execution time	Memory
27722		RayaBurong25_1	Cities (BOI16_cities)	C++14	100 / 100	2883 ms	45092 KiB

cities

#include <stdio.h>
#include <vector>
#include <queue>
#define INF 1000000000000000000LL
typedef struct node node;
struct node
{
	int v;
	long long w;
};
std::vector<node> AdjList[100005];
long long Cost[32][100005];
std::vector<node> Comp[32];
int Imp[5];
int N, K, M;
bool operator<(node a, node b)
{
	return (a.w > b.w);
}
long long min(long long a, long long b)
{
	return (a < b)?a:b;
}
std::priority_queue<node> Q;
void dijkstra(long long *A)
{
	int i, v, s;
	long long w;
	for (i = 1; i <= N; i++)
		Q.push({i, A[i]});

	node p;
	while (!Q.empty())
	{
		p = Q.top();
		Q.pop();

		if (p.w > A[p.v])
			continue;
		s = AdjList[p.v].size();
		for (i = 0; i < s; i++)
		{
			v = AdjList[p.v][i].v;
			w = p.w + AdjList[p.v][i].w;
			if (w < A[v])
			{
				A[v] = w;
				Q.push({v, w});
			}
		}
	}
}
int main()
{
	// freopen("test.in", "r", stdin);
	// freopen("test.out", "w", stdout);
	int twoK;
	scanf("%d %d %d", &N, &K, &M);
	twoK = (1 << K);
	int i, j, k, u, v;
	long long w;
	for (i = 0; i < K; i++)
	{
		scanf("%d", &Imp[i]);
	}
	for (i = 0; i < M; i++)
	{
		scanf("%d %d %lld", &u, &v, &w);
		AdjList[u].push_back({v, w});
		AdjList[v].push_back({u, w});
	}
	// printf(".\n");
	for (i = 1; i < twoK; i++)
	{
		for (j = i + 1; j < twoK; j++)
		{
			k = i|j;
			if (k > j)
				Comp[k].push_back({i, j});
		}
	}
	// printf(".\n");
	for (i = 0; i < K; i++)
	{
		k = (1 << i);
		for (j = 1; j <= N; j++)
			Cost[k][j] = INF;
		Cost[k][Imp[i]] = 0;
		dijkstra(&Cost[k][0]);
		// printf("i%d\n", i);
	}
	for (i = 1; i < twoK; i++)
	{
		// printf("i %d\n", i);
		if (Comp[i].size() == 0)
			continue;
		for (j = 1; j <= N; j++)
		{
			Cost[i][j] = INF;
			for (k = 0; k < Comp[i].size(); k++)
				Cost[i][j] = min(Cost[i][j], Cost[Comp[i][k].v][j] + Cost[(int) Comp[i][k].w][j]);
		}
		dijkstra(&Cost[i][0]);
		// for (j = 1; j <= N; j++)
		// 	printf("%lld ", Cost[i][j]);
		// printf("\n");
	}
	long long Ans = INF;
	for (i = 1; i <= N; i++)
		Ans = min(Ans, Cost[twoK - 1][i]);
	printf("%lld", Ans);
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:100:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (k = 0; k < Comp[i].size(); k++)
                  ^
cities.cpp:58:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &N, &K, &M);
                               ^
cities.cpp:64:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &Imp[i]);
                       ^
cities.cpp:68:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %lld", &u, &v, &w);
                                  ^

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