結果

問題 No.1602 With Animals into Institute 2
コンテスト
ユーザー 👑 ygussany
提出日時 2021-06-06 15:59:44
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 353 ms / 4,000 ms
コード長 4,070 bytes
コンパイル時間 248 ms
コンパイル使用メモリ 33,792 KB
実行使用メモリ 19,416 KB
最終ジャッジ日時 2024-07-02 02:02:20
合計ジャッジ時間 6,957 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <stdio.h>
#include <stdlib.h>

typedef struct List {
	struct List *next;
	int v, id, cost, x;
} list;

const long long sup = 1LL << 60;

typedef struct {
	long long key;
	int id;
} data;
 
typedef struct {
	data *obj;
	int size;
} min_heap;
 
void push(data x, min_heap* h)
{
	int i = ++(h->size), j = i >> 1;
	data tmp;
	h->obj[i] = x;
	while (j > 0) {
		if (h->obj[i].key < h->obj[j].key) {
			tmp = h->obj[j];
			h->obj[j] = h->obj[i];
			h->obj[i] = tmp;
			i = j;
			j >>= 1;
		} else break;
	}
}

data pop(min_heap* h)
{
	int i = 1, j = 2;
	data output = h->obj[1], tmp;
	h->obj[1] = h->obj[(h->size)--];
	while (j <= h->size) {
		if (j < h->size && h->obj[j^1].key < h->obj[j].key) j ^= 1;
		if (h->obj[j].key < h->obj[i].key) {
			tmp = h->obj[j];
			h->obj[j] = h->obj[i];
			h->obj[i] = tmp;
			i = j;
			j = i << 1;
		} else break;
	}
	return output;
}

void Dijkstra(int N, int M, list* adj[], int s, long long dist[], int label[], int pred[], int depth[])
{
	int u, w;
	list *p;
	min_heap h;
	data d;
	h.size = 0;
	h.obj = (data*)malloc(sizeof(data) * (M * 2 + 1));
	for (u = 1; u <= N; u++) dist[u] = sup;
	dist[s] = 0;
	label[s] = 0;
	pred[s] = s;
	depth[s] = 0;
	d.key = 0;
	d.id = s;
	push(d, &h);
	while (h.size > 0) {
		d = pop(&h);
		u = d.id;
		if (d.key != dist[u]) continue;
		for (p = adj[u]; p != NULL; p = p->next) {
			w = p->v;
			if (dist[w] > dist[u] + p->cost) {
				dist[w] = dist[u] + p->cost;
				label[w] = label[u] ^ p->x;
				pred[w] = u;
				depth[w] = depth[u] + 1;
				d.key = dist[w];
				d.id = w;
				push(d, &h);
			}
		}
	}
	free(h.obj);
}

int get_root(int u, int root[])
{
	if (root[u] == u) return u;
	else {
		root[u] = get_root(root[u], root);
		return root[u];
	}
}

void solve(int N, int M, list* adj[], list e[], int s, long long ans[])
{
	int label[100001], pred[100001], depth[100001];
	long long dist[2][100001];
	Dijkstra(N, M, adj, s, dist[0], label, pred, depth);
	
	int i, j, u, w, q[100001], root[100001], head, tail;
	long long height[200001];
	list *p;
	min_heap h;
	data d;
	h.size = 0;
	h.obj = (data*)malloc(sizeof(data) * (M * 2 + 1));
	for (u = 1; u <= N; u++) {
		dist[1][u] = sup;
		root[u] = u;
	}
	for (i = 0; i < M; i++) {
		u = e[i*2].v;
		w = e[i*2+1].v;
		if (label[w] != (label[u] ^ e[i*2].x)) {
			height[i] = dist[0][u] + dist[0][w] + e[i*2].cost;
			d.key = height[i];
			d.id = i;
			push(d, &h);
		} else height[i] = sup;
	}
	while (h.size > 0) {
		d = pop(&h);
		i = d.id;
		if (d.key != height[i]) continue;
		u = get_root(e[i*2].v, root);
		w = get_root(e[i*2+1].v, root);
		for (tail = 0; u != w; tail++) {
			if (depth[u] >= depth[w]) {
				q[tail] = u;
				u = get_root(pred[u], root);
			} else {
				q[tail] = w;
				w = get_root(pred[w], root);
			}
		}
		for (head = 0; head < tail; head++) {
			u = q[head];
			root[u] = w;
			dist[1][u] = height[i] - dist[0][u];
		}
		for (head = 0; head < tail; head++) {
			u = q[head];
			for (p = adj[u]; p != NULL; p = p->next) {
				w = p->v;
				i = p->id;
				if (label[w] == (label[u] ^ p->x) && height[i] > dist[1][u] + dist[0][w] + p->cost) {
					height[i] = dist[1][u] + dist[0][w] + p->cost;
					d.key = height[i];
					d.id = i;
					push(d, &h);
				}
			}
		}
	}
	
	for (u = 1, i = 0; u <= N; u++) {
		if (label[u] != 0) ans[u] = dist[0][u];
		else ans[u] = dist[1][u];
	}
	free(h.obj);
}

int main()
{
	int i, k, N, M, K, u, w, c, x, bit[31];
	char X[31];
	list *adj[100001] = {}, e[400001];
	scanf("%d %d %d", &N, &M, &K);
	for (k = 1, bit[0] = 1; k < K; k++) bit[k] = bit[k-1] << 1;
	for (i = 0; i < M; i++) {
		scanf("%d %d %d %s", &u, &w, &c, X);
		for (k = 0, x = 0; k < K; k++) if (X[k] == '1') x |= bit[k];
		e[i*2].v = w;
		e[i*2+1].v = u;
		e[i*2].id = i;
		e[i*2+1].id = i;
		e[i*2].cost = c;
		e[i*2+1].cost = c;
		e[i*2].x = x;
		e[i*2+1].x = x;
		e[i*2].next = adj[u];
		e[i*2+1].next = adj[w];
		adj[u] = &(e[i*2]);
		adj[w] = &(e[i*2+1]);
	}
	
	long long ans[100001];
	solve(N, M, adj, e, N, ans);
	for (u = 1; u < N; u++) printf("%lld\n", (ans[u] == sup)? -1: ans[u]);
	fflush(stdout);
	return 0;
}
0