oj.uz

Submission #27722

# Submission time Handle Problem Language Result Execution time Memory
27722 2017-07-13T14:12:39 Z RayaBurong25_1 Cities (BOI16_cities) C++14
100 / 100
 2883 ms 45092 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 28520 KB Output is correct
2 Correct 0 ms 28520 KB Output is correct
3 Correct 0 ms 28520 KB Output is correct
4 Correct 0 ms 28520 KB Output is correct
5 Correct 0 ms 28520 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 863 ms 45092 KB Output is correct
2 Correct 883 ms 44968 KB Output is correct
3 Correct 593 ms 36880 KB Output is correct
4 Correct 126 ms 37504 KB Output is correct
5 Correct 519 ms 45064 KB Output is correct
6 Correct 83 ms 37400 KB Output is correct
7 Correct 3 ms 28652 KB Output is correct
8 Correct 3 ms 28652 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 28652 KB Output is correct
2 Correct 3 ms 28652 KB Output is correct
3 Correct 3 ms 28652 KB Output is correct
4 Correct 3 ms 28652 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1383 ms 45084 KB Output is correct
2 Correct 1639 ms 44704 KB Output is correct
3 Correct 1119 ms 36880 KB Output is correct
4 Correct 936 ms 42028 KB Output is correct
5 Correct 283 ms 40380 KB Output is correct
6 Correct 129 ms 40852 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2543 ms 45084 KB Output is correct
2 Correct 2796 ms 45068 KB Output is correct
3 Correct 2883 ms 44792 KB Output is correct
4 Correct 2109 ms 36884 KB Output is correct
5 Correct 1463 ms 42028 KB Output is correct
6 Correct 389 ms 40380 KB Output is correct
7 Correct 136 ms 40852 KB Output is correct