다익스트라 알고리즘을 사용하여 최단 경로의 값을 구한다.
BFS 알고리즘을 사용하여 최단 경로의 경로를 구한다.
BFS 알고리즘으로로 구한 경로를 삭제
다시 한번 다익스트라 알고리즘을 사용해서 거의 최단 경로를 구한다.
from collections import deque
import sys
import heapq
INF = 1e9
def dijkstra():
q = []
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
for i in graph[now]:
cost = dist + graph[now][i]
if cost < distance[i]:
distance[i] = cost
heapq.heappush(q, (cost, i))
def bfs():
q = deque()
q.append(destination) #반대로 탐색
while q:
v = q.popleft()
if v == start:
continue
for pre_v, pre_c in reversed_graph[v]:
if distance[pre_v] + graph[pre_v][v] == distance[v]: #목적지에서 최단거리 노드가 선택되면 총 합에서 그 간선의 거리를 뺀 것과 같다
if (pre_v, v) not in remove_list: #최단거리에 선택된 노드는 삭제
remove_list.append((pre_v, v))
q.append(pre_v)
while True: #테스트 케이스
n, m = map(int, sys.stdin.readline().split())
if n == 0 and m == 0: # 테스트 케이스 종료
break
start, destination = map(int, sys.stdin.readline().split())
graph = [dict() for _ in range(n)]
reversed_graph = [[] for _ in range(n)]
for _ in range(m):
u, v, p = map(int, sys.stdin.readline().split())
graph[u][v] = p
reversed_graph[v].append((u, p)) # 경로를 추적하기 위해서 역순 저장
# 다익스트라 알고리즘을 사용하여 최단 거리 찾기
distance = [INF] * n
dijkstra()
# BFS를 사용하여 최단 경로 추적
remove_list = list()
bfs()
# 최단 경로 제거
for u, v in remove_list:
del graph[u][v]
# 다익스트라 알고리즘을 사용하여 최종 최단 경로 찾기
distance = [INF] * n
dijkstra()
if distance[destination] == INF: # 거의 최단 경로가 없는 경우
print(-1)
else:
print(distance[destination])
#include <stdio.h>
#include <queue>
#include <algorithm>
#include <memory.h>
#define MAX 501
#define TMAX 10001
#define INF 100000000
using namespace std;
int N, K, S, D;
struct st { int to, d; };
struct st2 { int from, to, d; };
bool operator<(st a, st b)
{
return a.d > b.d;
}
priority_queue<st> pq;
vector<st> t[MAX], t2[MAX];
int d[MAX];
st2 v[TMAX]; // from,to저장
int k[MAX][MAX], visit[MAX];
int main()
{
#ifdef _DEBUG
freopen("c:\\study\\b5719.txt", "r", stdin);
#endif
while (1)
{
scanf("%d%d", &N, &K);
if (N == 0 && K == 0) break;
scanf("%d%d", &S, &D);
for (int i = 0; i < N; i++)
t[i].clear(), t2[i].clear();
for (int i = 0, a, b, c; i < K; i++)
scanf("%d%d%d", &a, &b, &c),
t[a].push_back({ b,c }), t2[b].push_back({ a,c }),
v[i] = { a,b,c };
pq.push({ S,0 });
memset(d, 0x3f, sizeof(d));
while (!pq.empty())
{
st n = pq.top(); pq.pop();
for (st next : t[n.to])
{
if (d[next.to] > n.d + next.d)
{
d[next.to] = n.d + next.d;
pq.push({ next.to, n.d + next.d });
}
}
}
if (d[D] == d[MAX - 1])
{
printf("-1\n");
continue;
}
// bfs로 최단경로 제외하고 경로 재설정
d[S] = 0;
queue<int> q;
q.push(D);
int cnt = 0;
memset(k, 0, sizeof(k));
memset(visit, 0, sizeof(visit));
while (!q.empty())
{
int node = q.front(); q.pop();
if (visit[node]) continue;
visit[node] = 1;
for (st next : t2[node])
if (d[next.to] + next.d == d[node])
q.push(next.to),
k[next.to][node] = 1; // 최단경로 저장
}
for (int i = 0; i < N; i++)
t[i].clear();
for (int i = 0; i < K; i++) // 거의최단경로 저장
if (k[v[i].from][v[i].to] == 0)
t[v[i].from].push_back({ v[i].to, v[i].d });
// 다시 다익스트라 돌림
pq.push({ S,0 });
memset(d, 0x3f, sizeof(d));
while (!pq.empty())
{
st n = pq.top(); pq.pop();
for (st next : t[n.to])
{
if (d[next.to] > n.d + next.d)
{
d[next.to] = n.d + next.d;
pq.push({ next.to, n.d + next.d });
}
}
}
if (d[D] == d[MAX - 1])
printf("-1\n");
else
printf("%d\n", d[D]);
}
}