다익스트라

C++

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

typedef struct Edge {
    int to, w;
} Edge;

typedef struct Node {
    int no, dist;
    bool operator< (const Node n) const {
        return dist > n.dist;
    }
} Node;

vector<Edge> edge[4001];
bool visited[4001];
int dist[4001];
priority_queue<Node> to_visit;

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; i++)
    {
        int A, B, C;
        scanf("%d%d%d", &A, &B, &C);
        edge[A].push_back({ B, C });
        redge[B].push_back({ A, C });
    }
    int S, E;
    scanf("%d%d", &S, &E);
    
    memset(visited, false, sizeof(visited));
    to_visit.push({ S, 0 });
    while (!to_visit.empty()) {
        Node curr = to_visit.top(); to_visit.pop();
        if (visited[curr.no]) continue;
        visited[curr.no] = true;
        dist[curr.no] = curr.dist;
        if (curr.no == E) break;
        for (vector<Edge>::iterator it = edge[curr.no].begin(); it != edge[curr.no].end(); it++) {
            if (!visited[it->to]) to_visit.push({ it->to, dist[curr.no] + it->w });
        }
    }
    
    printf("%d\n", dist[E]);
}

Swift

import Foundation

struct Node {
  let value: Int
  var adjacents = Array<(value: Int, weight: Int)>()
  var visited: Bool = false
  var distance: Int = 999_999_999
  
  init(_ value: Int) {
    self.value = value
  }
}

struct Graph {
  var nodes = [Node]()
  let numberOfNodes: Int
  
  init(numberOfNodes: Int) {
    self.numberOfNodes = numberOfNodes
    for i in 0..<numberOfNodes {
      nodes.append(Node(i))
    }
  }
  
  mutating func addEdge(firstNode: Int, secondNode: Int, weight: Int) {
    nodes[firstNode].adjacents.append((value: secondNode, weight: weight))
  }
  
  mutating func dijkstra(beginingNode: Int, visit: (Int, Int) -> Void) {
    var heap = Heap<(value: Int, distance: Int)>(capacity: numberOfNodes) { $0.distance < $1.distance }
    
    heap.push((value: beginingNode, distance: 0))
    
    while heap.size != 0 {
      guard let curr = heap.pop() else { continue }
      if nodes[curr.value].visited { continue }
      visit(curr.value, curr.distance)
      nodes[curr.value].visited = true
      nodes[curr.value].distance = curr.distance
      
      nodes[curr.value].adjacents.filter {
        nodes[$0.value].visited == false
      }.forEach {
        heap.push((value: $0.value, distance: min(nodes[$0.value].distance, nodes[curr.value].distance + $0.weight)))
      }
    }
  }
  
  mutating func reset() {
    for i in 0..<nodes.count {
      nodes[i].visited = false
      nodes[i].distance = 999_999_999
    }
  }
  
  struct Heap<Element> {
    private var storage: Array<Element?>
    private var firstIsCloseToIdeal: (Element, Element) -> Bool
    
    init(capacity: Int, firstIsCloseToIdeal: @escaping (Element, Element) -> Bool) {
      storage = Array<Element?>(repeating: nil, count: capacity + 1)
      self.firstIsCloseToIdeal = firstIsCloseToIdeal
    }
    var size: Int = 0
    func top() -> Element? {
      storage[1]
    }
    @discardableResult mutating func push(_ element: Element) -> Bool {
      guard size < storage.count - 1 else { return false }
      var index = size + 1
      storage[index] = element
      while index > 1 {
        guard let parent = storage[index / 2], let current = storage[index], firstIsCloseToIdeal(parent, current) == false else { break }
        storage.swapAt(index / 2, index)
        index /= 2
      }
      size += 1
      return true
    }
    mutating func pop() -> Element? {
      guard let top = self.top() else { return nil }
      storage.swapAt(1, size)
      storage[size] = nil
      size -= 1
      var index = 1
      while index * 2 <= size, let leftChild = storage[index * 2] {
        var idealChildIndex = index * 2
        if index * 2 + 1 <= size, let rightChild = storage[index * 2 + 1], firstIsCloseToIdeal(rightChild, leftChild) {
          idealChildIndex += 1
        }
        guard let current = storage[index], let idealChild = storage[idealChildIndex], firstIsCloseToIdeal(idealChild, current) else { break }
        storage.swapAt(idealChildIndex, index)
        index = idealChildIndex
      }
      return top
    }
  }
}