우선순위 큐를 사용한 다익스트라, 플로이드 워셜 복습

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> arr[101];
int table[101];
int solve(int start, int end)
{
    priority_queue<pair<int, int>> q;
    q.push({0, start});
    table[start] = 0;
    while(!q.empty())
    {
        int shortest = q.top().second;
        int dist = q.top().first;
        q.pop();
        if(dist > table[shortest]) continue;
        for(int i=0; i<arr[shortest].size(); i++)
        {
            int cost = table[shortest] + 1;
            if(table[arr[shortest][i]] > cost)
            {
                table[arr[shortest][i]] = cost;
                q.push({-cost, arr[shortest][i]});
            }
        }
        
    }
    return table[end];
}

int main()
{
    int n, m, from, to, via, end;
    cin >> n >> m;
    for(int i=0; i<m; i++)
    {
        cin >> from >> to;
        arr[from].push_back(to);
        arr[to].push_back(from);
    }
    cin >> end >> via;
    int result = 0;
    fill(table, table + 101, 1e9);
    result += solve(1, via);
    fill(table, table + 101, 1e9);
    result += solve(via, end);
    if(result >= 1e9)
        cout << -1;
    else
        cout << result;
    return 0;
}

// 플로이드 워셜 먼저 작성
// 문제 풀어보기
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n, m, begin, end, map[101][101], via, to;
    cin >> n >> m;
    for(int i=0; i<101; i++)
        fill(map[i], map[i] + 101, 1e9);
    
    for(int i=0; i<m; i++)
    {
        cin >> begin >> end;
        map[begin][end] = 1;
        map[end][begin] = 1;
    }
    cin >> to >> via;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            for(int k=1; k<=n; k++)
            {
                if(j == k)
                {
                    map[j][k] = 0;
                    continue;
                }
                
                map[j][k] = min(map[j][k], map[j][i] + map[i][k]);
                
            }
        }
    }
    
    int result = 0;
    result += map[1][via];
    result += map[via][to];
    if(result >= 1e9)
        cout << -1;
    else
        cout << result;
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<pair<int, int>> arr[30001];
int table[30001];
void solve(int start)
{
    priority_queue<pair<int, int>> q;
    table[start] = 0;
    q.push({0, start});
    
    while(!q.empty())
    {
        int time = q.top().first;
        int shortest = q.top().second;
        q.pop();
        
        if(time < table[shortest]) continue;
        
        for(int i=0; i<arr[shortest].size(); i++)
        {
            int cost = table[shortest] + arr[shortest][i].first;
            if(cost > table[arr[shortest][i].second])
            {
                table[arr[shortest][i].second] = cost;
                q.push({cost, arr[shortest][i].second});
            }
        }
    }
}
int main()
{
    int n, m, start, begin, end, time;
    cin >> n >> m >> start;
    for(int i=0; i<m; i++)
    {
        cin >> begin >> end >> time;
        arr[begin].push_back({time, end});
    }
    fill(table, table + 30001, -1e9);
    solve(start);
    int max = -21e8, cnt = 0;
    for(int i=1; i<=n; i++)
    {
        if(table[i] < 1e9 && i != start)
            cnt++;
        if(max < table[i])
            max = table[i];
    }
    cout << cnt << ' ' << max;
    return 0;
    
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<pair<int, int>> arr[30001];
int table[30001];

void solve(int start)
{
    priority_queue<pair<int, int>> q;
    q.push({0, start});
    table[start] = 0;
    
    while(!q.empty())
    {
        int dist = -q.top().first;
        int now = q.top().second;
        q.pop();
        
        if(dist > table[now]) continue;
        for(int i=0; i<arr[now].size(); i++)
        {
            int cost = table[now] + arr[now][i].second;
            if(table[arr[now][i].first] > cost)
            {
                table[arr[now][i].first] = cost;
                q.push({-cost, arr[now][i].first});
            }
        }
    }
}
int main()
{
    int n, m, start, from, to, time;
    cin >> n >> m >> start;
    for(int i=0; i<m; i++)
    {
        cin >> from >> to >> time;
        arr[from].push_back({to, time});
    }
    fill(table, table + 30001, 1e9);
    solve(start);
    
    int cnt = 0, max = -1e9;
    for(int i=1; i<=n; i++)
    {
        if(table[i] >= 1e9)
            continue;
        cnt++;
        if(max < table[i])
            max = table[i];
    }
    cout << cnt-1 << ' ' << max;
    return 0;
}