[SWEA] 5684 운동

출처: SWEA 

 Input 

1      

3 4    

1 2 1  

3 2 1  

1 3 5

2 3 2

 

 Output 

#1 3

 

N이 크지 않아 DFS 혹은 BFS로도 풀이 가능

다익스트라 알고리즘 이용

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define SIZE 401
#define INF 987654321
using namespace std;
 
struct Pair {
    int v, w;
    Pair(int v, int w) : v(v), w(w) {}
};
 
struct minHeap {
    bool operator()(Pair p1, Pair p2) {
        return p1.w > p2.w;
    }
};
 
int n, m, answer;
int dist[SIZE];
vector<Pair> graph[SIZE];
 
int dijkstra(int u) {
    priority_queue<Pair, vector<Pair>, minHeap> pq;
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
    }
 
 
    pq.push(Pair(u, 0));
    while (!pq.empty()) {
        Pair cur = pq.top(); pq.pop();
        for (Pair next : graph[cur.v]) {
            int nd = cur.w + next.w;
            if (dist[next.v] > nd && nd < answer) {
                dist[next.v] = nd;
                pq.push(Pair(next.v, nd));
            }
        }
    }
    return dist[u];
}
 
#include <iostream>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
 
    int testCase; cin >> testCase;
    for (int tc = 1; tc <= testCase; ++tc) {
        for (int i = 0; i < n; i++) {
            graph[i].clear();
        }
        cin >> n >> m;
        int s, e, d;
        for (int i = 0; i < m; i++) {
            cin >> s >> e >> d;
            graph[s-1].push_back(Pair(e-1, d));
        }         
 
        answer = INF;
        for (int i = 0; i < n; i++) {
            answer = min(answer, dijkstra(i));
        }
        if (answer == INF) answer = -1;
 
 
        // 정답 출력
        printf("#%d %d\n", tc, answer);
    }
}