Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

BOJ-5719-거의 최단 경로 #57

Open
changicho opened this issue Jan 15, 2020 · 0 comments
Open

BOJ-5719-거의 최단 경로 #57

changicho opened this issue Jan 15, 2020 · 0 comments
Labels
clear 정답코드
Milestone

Comments

@changicho
Copy link
Owner

5719. 거의 최단 경로

링크

난이도 정답률(_%)
Gold I 28.931

설계

두 번째 최단 경로를 구하는 방법

  1. 다이크스트라
  2. 간선지우기
  3. 다이크스트라

정리

내 코드 (ms) 빠른 코드 (ms)
52

고생한 점

컴파일 에러

memset 함수를 사용하기 위해선 cstring 헤더를 include해야한다.

코드

#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>

#define INF 987654321

using namespace std;

int V, E;
int start, destination;

int graph[502][502];
int costs[502];

void dijkstra(int start) {
	// initialize
	memset(costs, -1, sizeof(costs));

	priority_queue<pair<int, int> > pq;
	pq.push({ 0,start });

	while (!pq.empty()) {
		int here = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();

		if (costs[here] != -1) continue;

		costs[here] = cost;

		for (int i = 0; i < V; i++) {
			if (graph[here][i] == -1) continue;
			if (costs[i] != -1) continue;

			pq.push({ -(cost + graph[here][i]), i });
		}
	}
	return;
}

void eraseEdge(int destination) {
	queue<int> q;
	q.push(destination);

	while (!q.empty()) {
		int current = q.front();
		q.pop();

		for (int i = 0; i < V; i++) {
			if (costs[current] == costs[i] + graph[i][current] && graph[i][current] != -1) {
				graph[i][current] = -1;
				q.push(i);
			}
		}
	}
	return;
}

void solution() {
	while (true) {
		memset(graph, -1, sizeof(graph));

		cin >> V >> E;
		if (V == 0 && E == 0) break;

		cin >> start >> destination;

		for (int i = 0; i < E; i++) {
			int from, to, cost;
			cin >> from >> to >> cost;

			graph[from][to] = cost;
		}

		dijkstra(start);
		eraseEdge(destination);
		dijkstra(start);

		cout << costs[destination] << "\n";
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	solution();

	return 0;
}

@changicho changicho added the clear 정답코드 label Jan 15, 2020
@changicho changicho added this to the day7 milestone Jan 15, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
clear 정답코드
Projects
None yet
Development

No branches or pull requests

1 participant