글 읽기 - 반례를 모르겠어요

kdr06006 4년 전 0

1번을 시작점으로 다익스트라,

N번을 시작점으로 다익스트라해서 구했는데 뭐가 틀린걸까요?

#include<stdio.h>
#include<malloc.h>
#define _size 100001
#define LL long long
#define heap link[0]

typedef struct Link {
	int cur;
	LL dis;
}L;
L* link[_size];
int size[_size], cap[_size], h[_size];//height
const LL INF = 1e14;
LL dis[2][_size];

inline void swap(L& a, L& b) { L temp = a; a = b; b = a; }
inline LL max(LL a, LL b) { return a > b ? a : b; }

void re(int idx, L a)
{
	if (++size[idx] >= cap[idx]) {
		link[idx] = (L*)realloc(link[idx], sizeof(L) * (cap[idx] += 10));
	}
	link[idx][size[idx] - 1] = a;
}

void up(int idx)
{
	if (idx == 0) return;
	int par = (idx - 1) / 2;
	if (heap[idx].dis < heap[par].dis) {
		swap(heap[idx], heap[par]);
		up(par);
	}
}

void down(int idx)
{
	int cha = idx, L = idx * 2 + 1, R = idx * 2 + 2;
	if (L<size[0] && heap[cha].dis>heap[L].dis) cha = L;
	if (R<size[0] && heap[cha].dis>heap[R].dis) cha = R;
	if (idx != cha) {
		swap(heap[idx], heap[cha]);
		down(cha);
	}
}

void push(L a)
{
	re(0, a);
	up(size[0] - 1);
}

L pop()
{
	L temp = heap[0];
	heap[0] = heap[--size[0]];
	down(0);
	return temp;
}

void BFS(int idx)
{
	while (size[0]) {
		L cur = pop();
		for (int i = 0; i < size[cur.cur]; i++) {
			L next = link[cur.cur][i];
			if (h[cur.cur] < h[next.cur]) {
				if (dis[idx][next.cur] > dis[idx][cur.cur] + next.dis) {
					dis[idx][next.cur] = dis[idx][cur.cur] + next.dis;
					push({ next.cur,dis[idx][next.cur] });
				}
			}
		}
	}
}

int main(void)
{
	int N, M, H, A;//health,achievement
	scanf("%d %d %d %d", &N, &M, &H, &A);
	for (int i = 0; i <= N; i++) link[i] = (L*)malloc(sizeof(L));

	for (int i = 1; i <= N; i++) {
		scanf("%d", &h[i]);
		dis[0][i] = dis[1][i] = INF;
	}

	int n1, n2, n3;
	while (M--) {
		scanf("%d %d %d", &n1, &n2, &n3);
		re(n1, { n2,n3 });
		re(n2, { n1,n3 });
	}

	dis[0][1] = 0;;
	push({ 1,0 });
	BFS(0);

	size[0] = 0;
	dis[1][N] = 0;;
	push({ N,0 });
	BFS(1);

	LL res = -INF;
	for (int i = 2; i <= N - 1; i++) {
		if (dis[0][i] == INF || dis[1][i] == INF) continue;
		LL temp = h[i] * A - (dis[0][i] + dis[1][i]) * H;
		res = max(res, temp);
	}

	res == -INF ? puts("Impossible") : printf("%lld\n", res);


	for (int i = 0; i <= N; i++) free(link[i]);
}

kdr06006 4년 전 0

16번째줄 swap실수였습니다

해결했습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 모르겠어요

kdr06006 4년 전 0

kdr06006 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말