(BOJ, 1753) 최단경로 (No Library)

다익스트라 알고리즘 ( BFS(Adjacent List + myalloc 활용) + Heap)

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int V, E, K;
struct link {
	int index;
	int weigh;
	struct link* next;
};
struct link tree[20001];

struct link myalloc[300000];
int alloc_cnt = 0;
inline struct link* l_alloc() { return &myalloc[alloc_cnt++]; };

int ans[20001];

struct state {
	int index;
	int weigh;
};
struct state heap_alloc[300000];
int h_alloc_cnt = 0;
inline struct state* h_alloc() { return &heap_alloc[h_alloc_cnt++]; };
struct state* heap[300000];
int heap_size = 0;
// 힙
void push(struct state* val) {
	int t = ++heap_size;
	while (t > 1) {
		if (val->weigh < heap[t/2]->weigh) {
			heap[t] = heap[t / 2];
			t /= 2;
		}
		else break;
	}
	heap[t] = val;
}
struct state* pop() {
	struct state* ret = heap[1];
	struct state* v = heap[heap_size--];
	int parent = 1, child = 2;
	while (child <= heap_size) {
		if (child + 1 <= heap_size)
			if (heap[child]->weigh > heap[child + 1]->weigh) child++;
		if (v->weigh > heap[child]->weigh) {
			heap[parent] = heap[child];
			parent = child;
			child = parent * 2;
		}
		else break;
	}
	heap[parent] = v;
	return ret;
}

void bfs() {
	struct state* tmp = h_alloc();
	tmp->index = K;
	tmp->weigh = 0;
	push(tmp);
	while (heap_size) {
		struct state* v = pop();
		
		struct link* t = tree[v->index].next;
		while (t) {
			if (ans[t->index] == -1 || t->weigh + v->weigh < ans[t->index]) {
				struct state* next = h_alloc();
				next->index = t->index;
				next->weigh = v->weigh + t->weigh;
				ans[next->index] = next->weigh;
				push(next);
			}
			t = t->next;
		}
	}
}

int main() {
	int u, v, w;
	scanf("%d %d", &V, &E);
	scanf("%d", &K);
	for (register int i = 0; i < E; i++) {
		scanf("%d %d %d", &u, &v, &w);
		struct link* t = l_alloc();
		t->weigh = w;
		t->index = v;
		t->next = tree[u].next;
		tree[u].next = t;
	}
	
	for (register int i = 1; i <= V; i++)
		ans[i] = -1;

	bfs();
	for (register int i = 1; i <= V; i++) {
		if (i == K)printf("0\n");
		else if (ans[i] == -1) printf("INF\n");
		else printf("%d\n", ans[i]);
	}

	return 0;
}