[1956번] 운동

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 플로이드 워셜 :: http://www.crocus.co.kr/search/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C

이 문제는 사이클이 존재하는지 찾고, 사이클이 존재한다면 가장 최솟값을 가지는 사이클 값을 구해달라는 문제이다.

플로이드 워셜을 이용한 풀이 방법은 두가지 풀이 방법이 존재한다.

1. 자기 자신 노드의 최단 거리를 0으로 설정한 경우

플로이드 워셜에서 사이클에 대한 최단 거리를 업데이트 해줄 수 없다.

따라서 직접 사이클이 존재하는지 찾아봐주는 조건을 작성해주어야 한다.

아래 코드에서 if(graph[j][i] != INF) 코드와 처음 입력부분의 if(graph[to][from] != INF) 이 두 부분이다.

j, i 부분이 INF가 아니라는 의미는 i->j , j->i가 서로 존재하는 것이니 사이클이 생기는 것이고

to,from부분이 INF가 아니라는 의미또한 사이클이 있다는 의미다.

2. 자기 자신 노드의 최단 거리를 INF로 설정한 경우

최단 거리를 이용하여 갱신된다면 자기 자신으로 돌아오는 루트가 있다는 것이고, 결국 최솟값은 graph[i][i]의 값 중

최솟값을 찾으면 된다는 의미이다.

소스 코드 : 

(자기 자신 노드의 최단 거리를 0으로 설정한 경우)

#include <stdio.h>
#include <limits.h>
 
#define MAX_V 410
#define min(a,b) (a < b ? a : b)
 
// 정점의 수를 지정한다.
int V;
 
// INF를 무한대라고 지정하고, INT_MAX를 이용한다.
#define INF 987654321
 
int minVal = INF;
int graph[MAX_V][MAX_V];
 
// 모든 경로에 대한 최단 거리를 찾아주는 플로이드 워셜 함수
void floydWarshall()
{
    // 한 점을 경유하여
    for (int k = 1; k <= V; k++)
    {
        // x에서
        for (int i = 1; i <= V; i++)
        {
            // y로 갈때
            for (int j = 1; j <= V; j++)
            {
                // 최단거리면 업데이트 해준다.
                if (graph[i][k] + graph[k][j] < graph[i][j])
                {
                    graph[i][j] = graph[i][k] + graph[k][j];
 
                    if (graph[j][i] != INF)
                        minVal = min(minVal, graph[i][j] + graph[j][i]);
                }
            }
        }
    }
}
 
 
int main()
{
    int from, to, val, n;
 
    scanf("%d", &V);
    scanf("%d", &n);
 
    V++;
 
    for (int i = 1; i <= V; i++)
        for (int j = 1; j <= V; j++)
            i == j ? graph[i][j] = 0 : graph[i][j] = INF;
 
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d %d", &from, &to, &val);
        graph[from][to] = val;
 
        if (graph[to][from] != INF)
            minVal = min(minVal, graph[from][to] + graph[to][from]);
    }
 
    // 플로이드 워셜 알고리즘으로 진입
    floydWarshall();
 
    minVal == INF ? printf("-1") : printf("%d", minVal);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

( 자기 자신 노드의 최단 거리를 INF로 설정한 경우 )

#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
const int INF = 987654321;
const int MAX_V = 400;
 
int V, E;
int dist[MAX_V + 1][MAX_V + 1];
 
int main() {
    scanf("%d%d", &V, &E);
 
    for (int i = 1; i <= V; i++) {
        for (int j = 1; j <= V; j++) {
            dist[i][j] = INF;
        }
    }
 
    for (int i = 0; i < E; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        dist[a][b] = min(dist[a][b], c);
    }
 
    for (int k = 1; k <= V; k++) {
        for (int u = 1; u <= V; u++) {
            for (int v = 1; v <= V; v++) {
                dist[u][v] = min(dist[u][v], dist[u][k] + dist[k][v]);
            }
        }
    }
 
    int ans = INF;
    for (int i = 1; i <= V; i++) {
        ans = min(ans, dist[i][i]);
    }
 
    printf("%d", (ans == INF) ? -1 : ans);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>