문제

문제 링크 : https://www.acmicpc.net/problem/1956 (단계별로 풀어보기 : 최단 거리)

문제 풀이

해당 문제를 나는 플로이드와샬 알고리즘으로 접근하였다. 해당 문제는 정점의 개수가 적절히 제한되어 있으므로 시간복잡도가 높은 플로이드와샬 알고리즘을 적용하는 것이 가능하다. 문제를 요약하면 a에서 b로가는 거리c인 도로가 주어지면, 가장 작은 사이클(시작정점에서 다시 시작정점으로 돌아오는 최단거리)를 찾는 것이다. 플로이드 와샬 알고리즘을 (설명은 링크 참고바람) 사용하여 테이블을 갱신하면 각 정점에서 다른 정점으로 가는 최단거리를 얻을 수 있다. 그러면 테이블을 확인하여 시작정점 -> 다른정점 -> 시작정점 을 확인하여 최단거리를 얻을 수 있다. 처음 이 방식으로 알고리즘을 짜서 제출하였는데 실패했다. 실패 이유는 도로가 주어질 때 시작정점과 도착정점이 같아 한정점에서도 사이클이 생길 수 있다는 점이다. 이 점을 생각하여 테이블 갱신방식을 수정해주었다. 또한 사이클이 존재하지 않아 운동 경로를 찾지 못할 시 -1을 출력하는 부분을 수정하여 문제를 통과할 수 있었다.

알고리즘 스케치

소스코드

Floyd Warshall

#include <iostream>
#include <algorithm>
#include <vector>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define INF 1e10
#define ll long long
using namespace std;

vector <vector<ll>> table;
ll minvalue = INF;
int n, m;

void input();
void FloydWarshall();

int main()
{
    fastio;
    input();
    FloydWarshall();
    if(minvalue == INF)
        cout << -1;
    else
        cout << minvalue;
    return 0;
}

void input()
{
    cin >> n >> m;
    table.resize(n+1);
    for(int i=1; i<n+1; i++){
        table[i].resize(n+1);
        fill(table[i].begin(),table[i].end(),INF);
    }
    for(int i=1, j=1; i<=n; i++,j++) table[i][j]=0;
    int a,b,c;
    for(int i=0; i<m; i++){
        cin >> a >> b >> c;
        if(table[a][b]==0 || table[a][b]>c)   table[a][b] = c;
    }
}

void FloydWarshall()
{
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                table[i][j] = min(table[i][j], table[i][k]+table[k][j]);
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i==j){
                if(table[i][j]==0 || table[i][j]==0) continue;
                else{
                    minvalue = min(minvalue, table[i][j]);
                }
            } 
            else{
                minvalue = min(minvalue, table[i][j]+table[j][i]);
            }
        }
    }
}