BOJ 17835 면접보는 승범이네

출처 : https://www.acmicpc.net/problem/17835

아 이거 사실 증명 안하고 예전에 풀었던거 비슷하게 감으로 떄려 맞췄다.
그래서 정당성에 대한 설명은 못하겠고 풀이방법만 적을게.(누가 증명좀 ㅎ)

1. 역방향 그래프를 만든다.
2. 출발지는 면접장 전체다. -> pq, memo에 면접장 전부 반영해준다.
3. 다익스트라를 돌린다.
4. 그럼 memo[i]가 가장 큰게 문제에서 원하는 두번째 답dl다.
5. 첫번째 답은 돌골렘 대가리도 유추할수 있을것이다.

추가)

면접장과 모두 거리가 0인 간선으로 연결된 노드를 하나 만든 다음 해당 노드에서 다익스트라를 돌린다고 생각하면 memo[i]에 나온 결과는 임의의 면접장에서 i번 도시까지 가는 가장 짧은 거리가 된다. (새로만든노드 -> 면접장은 거리가 0이므로.) 위의 방법은 이와 동일.
-by lovinix

아래는 코드(사실상 니들은 100line 이후는 볼 필요 없다. 다익스트라 로직보다 pq 구현이 더 김. 이래서 내가 다익스트라 문제 풀기 싫음)
아 그리고 입력을 잘보자 후..... long long써야 된다.....
또 방문체크 안하면? tle ㅋ

#include<stdio.h>
#include<malloc.h>
struct e
{
	int num;
	long long cost;
};
struct e* elist[100010], heap[500050];
int answer, eindex[100010], vn, en, k, start[100010], hidx, v[100010];
long long memo[100010];
void input();
void pb(int, int, long long);
void di();
void push(int, long long);
struct e pop();
int get_mode(int);
struct e calc();
void fin();
void make_answer();
int main(void)
{
	make_answer();
	return 0;
}
void make_answer()
{
	struct e ret;
	input();
	di();
	ret = calc();
	fin();
	printf("%d\n", ret.num);
	printf("%lld\n", ret.cost);
}
void input()
{
	int a, b;
	long long c;
	scanf("%d %d %d", &vn, &en, &k);
	while (en--)
	{
		scanf("%d %d %lld", &a, &b, &c);
		pb(b, a, c);
	}
	for (a = 0; a < k; a++)
	{
		scanf("%d", &start[a]);
	}
	for (a = 1; a <= vn; a++)
	{
		memo[a] = 0x7fffffffffffffff;
	}
}
void di()
{
	int d, next;
	long long ncost;
	struct e pnode;
	for (d = 0; d < k; d++)
	{
		push(start[d], 0);
		memo[start[d]] = 0;
	}
	while (hidx)
	{
		pnode = pop();
		if (v[pnode.num])
		{
			continue;
		}
		for (d = 0; d < eindex[pnode.num]; d++)
		{
			next = elist[pnode.num][d].num;
			ncost = elist[pnode.num][d].cost;
			if (memo[next] > memo[pnode.num] + ncost)
			{
				memo[next] = memo[pnode.num] + ncost;
				push(next, memo[next]);
			}
		}
		v[pnode.num] = 1;
	}
}
struct e calc()
{
	int num, d;
	long long cost;
	struct e ret;
	for (d = 1, num = 111111, cost = -1; d <= vn; d++)
	{
		if (cost < memo[d])
		{
			cost = memo[d];
			num = d;
		}
	}
	ret.cost = cost;
	ret.num = num;
	return ret;
}
void pb(int a, int b, long long c)
{
	elist[a] = (struct e*)realloc(elist[a], sizeof(struct e) * (eindex[a] + 1));
	elist[a][eindex[a]].num = b;
	elist[a][eindex[a]++].cost = c;
}
void fin()
{
	int i;
	for (i = 0; i <= vn; i++)
	{
		if (elist[i])
		{
			free(elist[i]);
		}
	}
}
void push(int num, long long cost)
{
	int cidx, tidx;
	struct e temp;
	hidx++;
	heap[hidx].cost = cost;
	heap[hidx].num = num;
	cidx = hidx;
	tidx = cidx / 2;
	while (!(!tidx || heap[tidx].cost < heap[cidx].cost))
	{
		temp = heap[cidx];
		heap[cidx] = heap[tidx];
		heap[tidx] = temp;
		cidx = tidx;
		tidx = cidx / 2;
	}
}
struct e pop()
{
	int cidx, mode;
	struct e ret, left, temp, right;
	ret = heap[1];
	heap[1] = heap[hidx];
	hidx--;
	cidx = 1;
	while (1)
	{
		mode = get_mode(cidx);
		if (!mode)
		{
			break;
		}
		else if (mode == 1)
		{
			left = heap[cidx * 2];
			if (left.cost < heap[cidx].cost)
			{
				temp = heap[cidx];
				heap[cidx] = heap[cidx * 2];
				heap[cidx * 2] = temp;
				cidx *= 2;
			}
			else
			{
				break;
			}
		}
		else
		{
			left = heap[cidx * 2];
			right = heap[cidx * 2 + 1];
			if (left.cost < right.cost)
			{
				if (left.cost < heap[cidx].cost)
				{
					temp = heap[cidx];
					heap[cidx] = heap[cidx * 2];
					heap[cidx * 2] = temp;
					cidx *= 2;
				}
				else
				{
					break;
				}
			}
			else
			{
				if (right.cost < heap[cidx].cost)
				{
					temp = heap[cidx];
					heap[cidx] = heap[cidx * 2 + 1];
					heap[cidx * 2 + 1] = temp;
					cidx *= 2;
					cidx++;
				}
				else
				{
					break;
				}
			}
		}
	}
	return ret;
}
int get_mode(int idx)
{
	if (idx * 2 + 1 <= hidx)
	{
		return 2;
	}
	if (idx * 2 == hidx)
	{
		return 1;
	}
	return 0;
}