Submission #96230

#	Time	Username	Problem	Language	Result	Execution time	Memory
96230		ics0503	Cities (BOI16_cities)	C++17	37 / 100	6100 ms	44144 KiB

cities

#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
struct xy {
	long long x, y;
	bool operator<(const xy p)const {
		return x < p.x;
	}
};
vector<xy>edge[121212];
priority_queue<xy>H;
long long D[1 << 5][121212], L[6];
long long pls(long long a, long long b) { if (a == -1)return -1; if (b == -1)return -1; return a + b; }
long long min(long long a, long long b) { if (a == -1)return b; if (b == -1)return a; if (a < b)return a; return b;}
int  main() {
	long long n, m, k; scanf("%lld%lld%lld", &n, &k, &m);
	long long i, j;
	for (i = 0; i < k; i++)scanf("%lld", &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 });
	}
	for (i = 0; i < (1 << k); i++)for (j = 1; j <= n; j++)D[i][j] = -1;
	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 (long long p = 0; p < i; p++) if ((i | p) == i)D[i][j] = min(D[i][j], pls(D[p][j], D[i^p][j]));
		for (j = 1; j <= n; j++) if (D[i][j] != -1)H.push({ D[i][j],j });
		while (!H.empty()) {
			xy now = H.top(); H.pop();
			if (now.x != D[i][now.y])continue;
			for (j = 0; j < edge[now.y].size(); j++) {
				long long nxt = edge[now.y][j].x, w = edge[now.y][j].y;
				if (D[i][nxt] == -1 || D[i][nxt] > D[i][now.y] + w) {
					D[i][nxt] = D[i][now.y] + w;
					H.push({ D[i][nxt], nxt });
				}
			}
		}
	}
	long long ans = -1;
	for (i = 1; i <= n; i++)ans = min(ans, D[(1 << k) - 1][i]);
	printf("%lld", ans);
	return 0;
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
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:17:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  long long n, m, k; scanf("%lld%lld%lld", &n, &k, &m);
                     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:19: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("%lld", &L[i]);
                         ~~~~~^~~~~~~~~~~~~~~
cities.cpp:21: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 / 22
• Subtask 2: 0 / 14
• Subtask 3: 15 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26