[Baekjoon]1504_특정한최단경로

[Baekjoon]1504_특정한최단경로.c

/*
* [Baekjoon]1504_특정한최단경로
* 메모리 : 13504 KB
* 시간 : 160ms
*/
#pragma warning (disable:4996)
#include <stdio.h>
#include <malloc.h>

#define NSIZE 801
#define QSIZE 200001
#define INF 2e8+1

struct Edge {
	int node;
	int cost;
}q[NSIZE];

struct AdjList {
	struct Edge e;
	struct AdjList *next;
}adj_list[NSIZE];

int n, e;		// 정점과 간선의 개수
int n1, n2;		// 통과해야하는 두 정점
int lastnode = 0;
struct Edge heap[QSIZE * 2];
int short_dist[NSIZE];

void add_list(int s, int e, int c){
	struct AdjList *p = (struct AdjList*)calloc(1, sizeof(struct AdjList));
	p->e.node = e;
	p->e.cost = c;
	p->next = adj_list[s].next;
	adj_list[s].next = p;
}
void input() {
	int a, b, c;
	scanf("%d %d", &n, &e);
	for (int i = 0; i < e; ++i) {
		scanf("%d %d %d", &a, &b, &c);
		add_list(a, b, c);
		add_list(b, a, c);
	}
	scanf("%d %d", &n1, &n2);
}
void push_heap(struct Edge data) {
	heap[++lastnode] = data;
	int n, p;
	n = lastnode;
	p = lastnode / 2;
	while (n > 1) {
		if (heap[n].cost < heap[p].cost) {
			struct Edge temp = heap[n];
			heap[n] = heap[p];
			heap[p] = temp;
		}
		else {
			break;
		}
		n = p;
		p = n / 2;
	}
}
void pop_heap(struct Edge *data) {
	if (lastnode < 1) return ;
	*data = heap[1];
	heap[1] = heap[lastnode--];
	int n = 1;
	int lc, rc, c;
	lc = n * 2;
	rc = n * 2 + 1;
	while (1) {
		if (lc > lastnode) break;
		if(lc == lastnode) {
			c = lc;
		}
		else {
			c = heap[lc].cost < heap[rc].cost ? lc : rc;
		}

		if (heap[n].cost > heap[c].cost) {
			struct Edge temp = heap[n];
			heap[n] = heap[c];
			heap[c] = temp;
		}
		else {
			break;
		}
		n = c;
		lc = 2 * n;
		rc = 2 * n + 1;
	}
}
void find_short_distance(int start) {
	
	lastnode = 0;
	for (int i = 1; i <= n; ++i) {
		short_dist[i] = INF;
	}

	push_heap({ start,0 });
	int heap_size = 1;

 	while (heap_size > 0) {
		struct Edge cur;
		pop_heap(&cur);
		heap_size--;
		if (short_dist[cur.node] != INF) continue;
		// 시작점에서 현재 정점까지의 최소 비용 갱신
		short_dist[cur.node] = cur.cost;

		struct AdjList *p = &adj_list[cur.node];
		// 현재 정점과 연결되어있는 정점들 탐색
		for (;;) {
			p = p->next;
 			if (p == (struct AdjList*)0x0 ) {
				break;
			}
			if (short_dist[p->e.node] != INF) continue;
			push_heap({ p->e.node, short_dist[cur.node] + p->e.cost });
			heap_size++;
		}
	}
}
int solve() {
	// 1->n1 , 1->n2
	find_short_distance(1);
	int cost_n1 = short_dist[n1];
	int cost_n2 = short_dist[n2];

	// n1->n2 == n2->n1
	find_short_distance(n1);
	int cost_n1_n2 = short_dist[n2];
	
	// n1->n , n2->n
	find_short_distance(n);
	int cost_n2_n = short_dist[n2];
	int cost_n1_n = short_dist[n1];
	int cost_n = -1;


	if (cost_n1_n2 == INF) {
		cost_n = -1;
	}
	else if ((cost_n1 == INF || cost_n2_n == INF) && (cost_n2 == INF || cost_n1_n == INF)) {
		cost_n = -1;
	}
	else if (cost_n1 + cost_n1_n2 + cost_n2_n < cost_n2 + cost_n1_n2 + cost_n1_n) {
		cost_n = cost_n1 + cost_n1_n2 + cost_n2_n;
	}
	else{
		cost_n = cost_n2 + cost_n1_n2 + cost_n1_n;
	}
	return cost_n;
}
int main() {
	input();
	int answer = solve();
	printf("%d\n", answer);
}