oj.uz

Submission #96234

# Submission time Handle Problem Language Result Execution time Memory
96234 2019-02-07T11:26:58 Z ics0503 Cities (BOI16_cities) C++17
100 / 100
 2902 ms 49696 KB 
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
struct xy {
	long long x; int y;
	xy(long long x, int y) : x(x), y(y) {};
	bool operator<(const xy &p)const {
		return x > p.x;
	}
};
vector<xy>edge[121212];
long long D[1 << 5][121212];int L[6];
int  main() {
	int n, m, k; scanf("%d%d%d", &n, &k, &m);
	int i, j;
	for (i = 0; i < k; i++)scanf("%d", &L[i]);
	for (i = 0; i < m; i++) {
		long long s, e, w; scanf("%lld%lld%lld", &s, &e, &w);
		edge[s].push_back({ e,w });
		edge[e].push_back({ s,w });
	}
	long long inf = 1e18;
	for (i = 0; i < (1 << k); i++)for (j = 1; j <= n; j++)D[i][j] = inf;
	for (i = 0; i < k; i++)D[(1 << i)][L[i]] = 0;
	for (i = 1; i < (1 << k); i++) {
		for (j = 1; j <= n; j++) for (int p = 0; p < i; p++) if ((i | p) == i)D[i][j] = min(D[i][j], D[p][j]+D[i^p][j]);
		priority_queue<xy>H;
		for (j = 1; j <= n; j++) if (D[i][j]<inf)H.push({ D[i][j],j });
		while (!H.empty()) {
			xy now = H.top(); H.pop();
			for (j = 0; j < edge[now.y].size(); j++) {
				int nxt = edge[now.y][j].x, w = edge[now.y][j].y;
				if (D[i][nxt] > D[i][now.y] + w) {
					D[i][nxt] = D[i][now.y] + w;
					H.emplace(D[i][nxt], nxt);
				}
			}
		}
	}
	long long ans = inf;
	for (i = 1; i <= n; i++)ans = min(ans, D[(1 << k) - 1][i]);
	printf("%lld", ans);
	return 0;
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:21:28: warning: narrowing conversion of 'w' from 'long long int' to 'int' inside { } [-Wnarrowing]
   edge[s].push_back({ e,w });
                            ^
cities.cpp:22:28: warning: narrowing conversion of 'w' from 'long long int' to 'int' inside { } [-Wnarrowing]
   edge[e].push_back({ s,w });
                            ^
cities.cpp:33:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (j = 0; j < edge[now.y].size(); j++) {
                ~~^~~~~~~~~~~~~~~~~~~~
cities.cpp:16:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m, k; scanf("%d%d%d", &n, &k, &m);
               ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cities.cpp:18:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 0; i < k; i++)scanf("%d", &L[i]);
                         ~~~~~^~~~~~~~~~~~~
cities.cpp:20:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   long long s, e, w; scanf("%lld%lld%lld", &s, &e, &w);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 661 ms 26216 KB Output is correct
2 Correct 822 ms 30008 KB Output is correct
3 Correct 528 ms 20536 KB Output is correct
4 Correct 158 ms 15712 KB Output is correct
5 Correct 478 ms 25288 KB Output is correct
6 Correct 104 ms 15608 KB Output is correct
7 Correct 6 ms 3448 KB Output is correct
8 Correct 6 ms 3448 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3576 KB Output is correct
2 Correct 8 ms 3448 KB Output is correct
3 Correct 7 ms 3448 KB Output is correct
4 Correct 7 ms 3448 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1356 ms 32528 KB Output is correct
2 Correct 1314 ms 36332 KB Output is correct
3 Correct 711 ms 26784 KB Output is correct
4 Correct 767 ms 27604 KB Output is correct
5 Correct 260 ms 18260 KB Output is correct
6 Correct 124 ms 17912 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2902 ms 45328 KB Output is correct
2 Correct 2826 ms 49696 KB Output is correct
3 Correct 2786 ms 49200 KB Output is correct
4 Correct 1921 ms 39476 KB Output is correct
5 Correct 1589 ms 34036 KB Output is correct
6 Correct 436 ms 19800 KB Output is correct
7 Correct 164 ms 18068 KB Output is correct