Baekjoon 1956번 운동

문제

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

걸린 시간

01 : 04 : 02

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int v, e;
vector<vector<pair<int, int>>> adj;

int dijkstra(int src){
    vector<int> dist(v, INF);
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(src, 0));
    while(!pq.empty()){
        int here = pq.top().first;
        int cost = -pq.top().second;
        pq.pop();
        if(dist[here] < cost) continue;
        for(int i = 0; i < adj[here].size(); i++){
            int there = adj[here][i].first;
            int nextDist = cost + adj[here][i].second;
            if(nextDist < dist[there]){
                dist[there] = nextDist;
                pq.push(make_pair(there, -nextDist));
            }
        }
    }
    return dist[src];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> v >> e;
    adj.resize(v);
    int a, b, c;
    for(int i = 0; i < e; i++){
        cin >> a >> b >> c;
        adj[a-1].push_back(make_pair(b-1, c));
    }
    int ans = INF;
    for(int i = 0; i < v; i++)
        ans = min(ans, dijkstra(i));
    if(ans != INF) cout << ans;
    else cout << -1;
    return 0;
}

존재하는 여러 사이클 중 최단 경로를 찾아야 하므로 다익스트라 혹은 플로이드 와샬 알고리즘을 사용해야 한다.

시작지점을 0으로 초기화 하지 않고 최단 경로 알고리즘을 수행하면 최소 사이클의 도로 길이의 합을 구할 수 있다.

다익스트라를 사용한 풀이이다. (684ms)

다른 풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int v, e;
    cin >> v >> e;
    vector<vector<int>> adj(v, vector<int>(v, INF));
    int a, b, c;
    for(int i = 0; i < e; i++){
        cin >> a >> b >> c;
        adj[a-1][b-1] = c;
    }
    for(int k = 0; k < v; k++)
        for(int i = 0; i < v; i++)
            for(int j = 0; j < v; j++)
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
    int ans = INF;
    for(int i = 0; i < v; i++)
        ans = min(ans, adj[i][i]);
    if(ans != INF) cout << ans;
    else cout << -1;
    return 0;
}

분류의 플로이드 와샬 알고리즘으로도 풀어보았다. (100ms)