1753 최단경로

#include <bits/stdc++.h>
using namespace std;

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

    int v, e;
    cin >> v >> e;

    int start;
    cin >> start;

    int dist[20002];
    vector<pair<int, int>> graph[v + 1];
    for (int i = 1; i <= v; i++)
    {
        dist[i] = INF;
    }

    dist[start] = 0;

    for (int i = 0; i < e; i++)
    {
        int U, V, W;
        cin >> U >> V >> W;

        graph[U].push_back({V, W});
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    // 다익도 bfs로 작동
    pq.push({dist[start], start});
    // sort도 pq도 pair 볼때 first 먼저 봄

    while (!pq.empty())
    {
        auto [cost, cur] = pq.top(); // 이전노드에서 현재노드로 오는 정보
        // int cost = pq.top().first;
        // int cur = pq.top().second;
        pq.pop();

        if (cost > dist[cur])
            continue; // cur노드의 기존저장된 최단경로보다 현재의 cost가 더 크다면 continue;
        for (auto [nxt, ncost] : graph[cur])
        { // 현재 노드랑 연결된 노드 탐색
            if (dist[nxt] > ncost + cost)
            {                             // 다음노드의 현재 최단 경로보다 현재노드와 가중치를 더한 값이 더 적을 때
                dist[nxt] = ncost + cost; // 최단 경로 업데이트

                pq.push({dist[nxt], nxt}); // pq에 push
            }
        }
    }

    for (int i = 1; i <= v; i++)
    {
        if (dist[i] == INF)
            cout << "INF\\n";
        else
            cout << dist[i] << "\\n";
    }
    return 0;
}

11404 플로이드

#include <bits/stdc++.h>
using namespace std;

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

    int n, m;
    cin >> n >> m; // 도시개수n(노드), 도로개수m(간선)

    int dist[101][101];
    memset(dist, 0x3f, sizeof(dist)); // 0x3f 무지하게 큰 값
    // memset(배열, 값, 배열의 크기) << 배열을 값으로 배열의 크기만큼 채워줌

    for (int i = 1; i <= n; i++)
    {
        dist[i][i] = 0;
    }
    // 자기 자신의 경로는 0임.

    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = min(w, dist[u][v]);
        // 문제에서 경로가 하나가 아닐 수 있다고 함.
        // 최솟값을 넣어야 함.
    }

    // k i j for문을 기억하면 편함.

    // dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
    // k번째 노드를 경유할 때 기존의 최단경로와 비교해서 최단경로를 업데이트함/
    // 플로이드 워셜의 시간복잡도는 O(N^3).

    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (dist[i][j] > 10000000)
                dist[i][j] = 0; // 경로가 없을 때는 0으로 출력 (탐색이 안된거라 0x3f보다 큼)

            cout << dist[i][j] << " ";
        }
        cout << "\\n";
    }
    return 0;
}