1299 c++ - 전쟁-탈출편2

 

다익스트라 정리

 

다익스트라 풀이

1. 처음에 다익스트라로 n까지 최단 거리 구함. (구하면서 prev에 간선 정보들을 저장)
2. prev를 이용하여 graph에서 해당하는 간선들을 삭제.
3. 다시 다익스트라를 돌려서 n까지 가는 최단 거리를 구함.

고려한 점

1. 도시는 양방향으로 이동할 수 있다. (최단거리라면 양방향 둘 다 막힌다)
2. 다른 도시로 이동할 때 코스트가 다른 도로가 존재할 수 있다 ( 1->2 (1), 1->2 (2)) 이때 cost 가 1인 도로만 막힘
3. 탈출하지 못하는 경우는 없다.

정답 코드

#include <bits/stdc++.h>

using namespace std;

#define INF 1e9

void dijkstra(int n, vector<vector<pair<int, int>>>& graph,
              vector<int>& distance, vector<int>& prev) {
  priority_queue<pair<int, int>, vector<pair<int, int>>,
                 greater<pair<int, int>>>
      pq;

  distance.assign(n + 1, INF);
  prev.assign(n + 1, -1);

  distance[1] = 0;
  pq.push({0, 1});

  while (!pq.empty()) {
    int currentDist = pq.top().first;
    int currentNode = pq.top().second;
    pq.pop();

    if (currentDist > distance[currentNode]) {
      continue;
    }

    for (auto& edge : graph[currentNode]) {
      int nextNode = edge.first;
      int weight = edge.second;

      int newDist = currentDist + weight;
      if (newDist < distance[nextNode]) {
        distance[nextNode] = newDist;
        prev[nextNode] = currentNode;
        pq.push({newDist, nextNode});
      }
    }
  }
}

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

  int n, m;
  cin >> n >> m;

  vector<vector<pair<int, int>>> graph(n + 1);
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    graph[a].push_back({b, c});
    graph[b].push_back({a, c});
  }

  vector<int> distance(n + 1, INF);
  vector<int> prev(n + 1, -1);

  dijkstra(n, graph, distance, prev);

  vector<vector<pair<int, int>>> modifiedGraph = graph;

  int currentNode = n;
  while (prev[currentNode] != -1) {
    int from = prev[currentNode];
    int to = currentNode;
    int requiredCost = distance[to] - distance[from];

    modifiedGraph[from].erase(
        remove_if(modifiedGraph[from].begin(), modifiedGraph[from].end(),
                  [to, requiredCost](pair<int, int> edge) {
                    return edge.first == to && edge.second == requiredCost;
                  }),
        modifiedGraph[from].end());

    modifiedGraph[to].erase(
        remove_if(modifiedGraph[to].begin(), modifiedGraph[to].end(),
                  [from, requiredCost](pair<int, int> edge) {
                    return edge.first == from && edge.second == requiredCost;
                  }),
        modifiedGraph[to].end());

    currentNode = from;
  }

  dijkstra(n, modifiedGraph, distance, prev);

  cout << distance[n];

  return 0;
}