글 읽기 - 데이터를 추가해 주세요 [SPFA]

sait2000 3년 전 4

19897099과 15745887을 시간초과 내고 싶은 데이터입니다. tests-1753.zip

h0ngjun7 3년 전 0

SPFA 과정 중 Q 안에서 시작점으로부터의 거리가 가능하면 오름차순이 유지되도록 이러쿵 저러쿵 다른 최적화를 해보아도 저 2개를 다 뚫을 순 없네요ㅠㅠ

SPFA 기본 매커니즘을 잘 저격한 데이터라서 다익스트라 알고리즘처럼 최악이 보장된 알고리즘이 아니라면 어떻게 뚫을 수 있을지 잘 모르겠습니다.

#include <bits/stdc++.h>
using namespace std;

const int MAXV = 20005;

struct EDGE { int v, c; };
int d[MAXV], inQ[MAXV], del[MAXV];
vector <EDGE> g[MAXV];
deque <int> Q;

int main() {
	ios::sync_with_stdio(0);
	int V, E, K;
	cin >> V >> E >> K;
	for (int i = 0; i < E; i++) {
		int u, v, w; cin >> u >> v >> w;
		g[u].push_back({ v, w });
	}
	for (int i = 1; i <= V; i++) {
		d[i] = 2e9, inQ[i] = 0;
	}
	
	d[K] = 0;
	Q.push_back(K); inQ[K] = 1;
	while (!Q.empty()) {
		int p = 0;
		int u = Q.front(); Q.pop_front(); inQ[u]--;
		if (del[u]) {
			del[u]--;
			continue;
		}
		for (auto& e : g[u]) {
			int v = e.v, w = e.c;
			if (d[v] > d[u] + w) {
				d[v] = d[u] + w;

				if (inQ[v] == 0) {
					if (!Q.empty() && d[v] < d[Q.front()]) Q.push_front(v);
					else Q.push_back(v);
					inQ[v]++;
				}
				else if (!Q.empty() && d[v] < d[Q.front()]) {
					Q.push_front(v);
					inQ[v]++;
					del[v]++;
				}
			}
		}
	}
	for (int i = 1; i <= V; i++) {
		if (d[i] > 1e9) cout << "INF\n";
		else cout << d[i] << "\n";
	}
}

startlink 3년 전 0

재채점했습니다.

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

문제

문제

출처

ICPC

데이터를 추가해 주세요 [SPFA]

sait2000 3년 전 4

h0ngjun7 3년 전 0

startlink 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말