Submission #64382697

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <inttypes.h>
#define INF UINT64_C(0x4000000000000000)
struct edge_s {
  int to;
  uint64_t w;
};
int ec[16];
struct edge_s es[16][16];
int N;
uint64_t memo[16][1 << 16];
uint64_t calc(int node, int visited) {
  uint64_t ans = INF;
  int i;
  if ((visited >> node) & 1) return INF;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <inttypes.h>

#define INF UINT64_C(0x4000000000000000)

struct edge_s {
	int to;
	uint64_t w;
};

int ec[16];
struct edge_s es[16][16];

int N;

uint64_t memo[16][1 << 16];

uint64_t calc(int node, int visited) {
	uint64_t ans = INF;
	int i;
	if ((visited >> node) & 1) return INF;
	if (node == N) return 0;
	if (memo[node][visited]) return ~memo[node][visited];
	for (i = 0; i < ec[node]; i++) {
		uint64_t candidate = calc(es[node][i].to, visited | (1 << node)) ^ es[node][i].w;
		if (candidate < ans) ans = candidate;
	}
	return ~(memo[node][visited] = ~ans);
}

int main(void) {
	int M;
	int i;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	for (i = 0; i < M; i++) {
		int u, v;
		uint64_t w;
		if (scanf("%d%d%" SCNu64, &u, &v, &w) != 3) return 1;
		es[u][ec[u]++] = (struct edge_s){ v, w };
		es[v][ec[v]++] = (struct edge_s){ u, w };
	}
	printf("%" PRIu64 "\n", calc(1, 0));
	return 0;
}

Submission Info

Judge Result