글 읽기 - acm craft 다이스트라 질문이요!

rdd6584 6년 전 0

이 문제를 다이스트라 알고리즘으로 heap에 남아 있는 원소가 없어질때까지 반복하는 것으로 문제를 해결할 수 있었는데요.

~~플로이드 와샬이 제일 나을거 같기는 한데~~, 혹시 다이스트라나 비슷한 최단경로 알고리즘 중 이런 최장경로 문제를 더 쉽게 해결할 수 있는 방법이 있을까요?

아니면 최장경로 문제에서 그 외 DP나 DFS말고 다른 효율적인 방법이 있나요?

그리고 추가로 다이스트라는 단순히 BFS+우선순위 큐의 결합으로 정의될 수 있을까요?

고수분들 도와주세요.

#include<stdio.h>
#include<memory.h>

typedef struct {
	int o;
	int val;
} vertex;

char mat[1001][1001];
int vec[1001];
int visit[1001];
char st[1001];

vertex heap[100001];
vertex v, vt;
int top;

void push(vertex k) {
	int j;
	heap[++top] = k;
	j = top;

	while (heap[j].val < heap[j / 2].val) {
		k = heap[j];
		heap[j] = heap[j / 2];
		heap[j / 2] = k;
		j /= 2;
	}
}

vertex pop() {
	int t2;
	vertex t = heap[1], t3;
	heap[1] = heap[top--];

	for (int i = 1; i * 2 <= top; i = t2) {
		t2 = heap[i * 2].val < heap[i * 2 + 1].val ? i * 2 : i * 2 + 1;
		if (heap[i].val > heap[t2].val) {
			t3 = heap[t2];
			heap[t2] = heap[i];
			heap[i] = t3;
		}
	}

	return t;
}

int main() {
	int t, n, k, t1, t2, win;
	scanf("%d", &t);

	while (t--) {
		top = 0;
		memset(mat, 0, sizeof(mat));
		memset(st, 0, sizeof(st));
		memset(visit, 0, sizeof(visit));
		scanf("%d %d", &n, &k);

		for (int i = 1; i <= n; i++)
			scanf("%d", &vec[i]);

		for (int i = 0; i < k; i++) {
			scanf("%d %d", &t1, &t2);
			mat[t2][t1] = 1;
			st[t2] = 1; // st가 0일 경우, start노드
		}
		scanf("%d", &win);

		vt.val = vec[win];
		vt.o = win;
		visit[win]++;
		push(vt);

		while (top) {
			v = pop();
			if (visit[v.o] != 1) { visit[v.o]--; continue; } // 이 지점으로 가는 경로중 더 큰 경로가 있다면 continue

			for (int i = 1; i <= n; i++) {
				if (mat[v.o][i]) {
					vt.o = i;
					vt.val = v.val + vec[i];
					visit[i]++;
					push(vt);
				}
			}
			visit[v.o]--;
		}
		printf("%d\n", v.val);
	}
}