[BOJ] 5719 거의 최단 경로

문제: https://www.acmicpc.net/problem/5719

 

문제 풀이:

다익스트라 한 번 돌리고

뒤에서부터 최단 경로인 것들 다 지운 다음에

다익스트라 다시 돌림

소스코드:

#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
#include <string>
#define inf 5000001
using namespace std;

typedef pair<int, int> P;

int n, m,dist[501],adj[501][501];
bool visit[501];

void di(int start,int end) {
	fill(dist, dist + n+1, inf);
	priority_queue<P, vector<P>, greater<P>> pq;
	memset(visit, false, sizeof(visit));
	dist[start] = 0;
	pq.push({ 0,start });

	while (!pq.empty()) {
		int cur;
		do {
			cur = pq.top().second;
			pq.pop();
		} while (!pq.empty() && visit[cur]);

		if (visit[cur]) break;
		visit[cur] = true;

		for(int i=0;i<n;i++){
			if (cur != i && adj[cur][i] != -1) {
				if (dist[i] > dist[cur] + adj[cur][i]) {
					dist[i] = dist[cur] + adj[cur][i];
					pq.push({ dist[i] ,i});
				}
			}
		}
	}
}
void remove(int start, int end) {
	queue<int> q;
	q.push(end);

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

		for (int i = 0; i < n; i++) {
			if (cur != i && adj[i][cur] != -1) {
				if (dist[i] == dist[cur] - adj[i][cur]) {
					q.push(i);
					adj[i][cur] = -1;
				}
			}
		}
	}
}

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

	while (1) {
		cin >> n >> m;
		if (n == 0) break;

		memset(adj, -1, sizeof(adj));

		int start, end;
		cin >> start >> end;

		for (int i = 0; i < m; i++) {
			int q, w, e;
			cin >> q >> w >> e;
			adj[q][w] = e;
		}
		di(start, end);
		remove(start, end);
		di(start, end);
		if (dist[end] == inf) cout << "-1\n";
		else cout << dist[end] << '\n';
	}
	return 0;
}