[BaekJoon][1916] 최소비용 구하기

 BAEKJOON ONLINE JUDGE

1916 최소비용 구하기

https://www.acmicpc.net/problem/1916

 

그래프 최소비용 구하는 문제

1. 다익스트라

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
#define INF    1000000000
 
int n, m;
vector<pair<int, int>> vertex[1001];
priority_queue<pair<int, int>> pq;
int start, dest;
 
void input()
{
    int from, to, cost;
 
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d\n", &from, &to, &cost);
        vertex[from].push_back(make_pair(to, cost));
    }
 
    scanf("%d %d", &start, &dest);
}
 
int dijkstra(int src)
{
    vector<int> dist(n + 1, INF);
 
    dist[src] = 0;
    pq.push(make_pair(0, src));
 
    while (!pq.empty()) {
        int current = pq.top().second;
        int currentcost = pq.top().first * -1;
        pq.pop();
 
        if (currentcost <= dist[current]) {
            for (int i = 0; i < vertex[current].size(); i++) {
                int next = vertex[current][i].first;
                int cost = vertex[current][i].second;
 
                if (currentcost + cost < dist[next]) {
                    dist[next] = currentcost + cost;
                    pq.push(make_pair(dist[next] * -1, next));
                }
            }
        }
    }
 
    return dist[dest];
}
 
int main()
{
    input();
 
    printf("%d\n", dijkstra(start));
    
    return 0;
}

2. 플로이드

#include <stdio.h>
 
#define INF    1000000000
 
int n, m;
int vertex[1001][1001];
int start, dest;
 
void init()
{
    int i, j;
 
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            vertex[i][j] = INF;
        }
    }
}
 
void input()
{
    int from, to, cost;
 
    scanf("%d %d", &n, &m);
 
    init();
 
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d\n", &from, &to, &cost);
        if(cost < vertex[from][to])        vertex[from][to] = cost;
    }
 
    scanf("%d %d", &start, &dest);
}
 
void floyd()
{
    int i, j, k;
 
    for (k = 1; k <= n; k++) {
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                if (vertex[i][k] + vertex[k][j] < vertex[i][j]) {
                    vertex[i][j] = vertex[i][k] + vertex[k][j];
                }
            }
        }
    }
}
 
int main()
{
    input();
 
    floyd();
 
    printf("%d\n", vertex[start][dest]);
 
    return 0;
}

다익스트라에서는 인접리스트, 플로이드에서는 인접행렬으로 구현하였다.

인접리스트의 경우 중복이 들어오면 다 리스트에 넣어버렸지만

인접행렬의 경우 마지막 입력을 저장하였기 때문에

그냥 입력을 받았을 때 정답을 통과하지 못하였다.

나중에는 작은 비용만 저장을 하여 통과