[알고리즘] 운동

구현 방식

• 플로이도 와샬 방식으로 풀고, i 에서 i 로 가는 최단거리를 다시 구한다.
• 나는 맨처음에 FloydWarshall 함수에서 graph[i][i]를 통해 i 에서 i 로 가는 최단거리도 자동으로 구해지니까, 그냥,, solution 함수에서 한번더 i 에서 i 로 가는 최단거리를 다시 구하는 동작을 안해도 될것이라고 생각을 했는데
• 마지막 결론으로 나온 최단거리를 사용해서, i –> i를 가는 최단거리가 갱신이 될수도 잇을것같다. 반례를 찾으려했지만 실패

#include <string>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <limits.h>

using namespace std;

void solution(int V, vector<vector<long long>>& graph);
void FloydWarshall(int V, vector<vector<long long>>& graph);

int main()
{
    int V,E;
    cin >> V >> E;
    vector<vector<long long>> graph = vector<vector<long long>>(V + 1, vector<long long>(V + 1, LLONG_MAX));
    for (int i = 1; i <= E; i++)
    {
        int from, to, w;
        cin >> from >> to >> w;
        graph[from][to] = w;
    }

    solution(V, graph);
}

void solution(int V, vector<vector<long long>>& graph)
{
    FloydWarshall(V, graph);
    long long result = LLONG_MAX;
    for (int v = 1; v <= V; v++)
        for (int i = 1; i <= V; i++)
        {
            if (v == i)
                continue;
            if (graph[i][v] == LLONG_MAX || graph[v][i] == LLONG_MAX)
                continue;
            result = min(result, graph[i][v] + graph[v][i]);
        }

    if(result == LLONG_MAX)
        cout << -1 << endl;
    else
        cout << result << endl;

}

void FloydWarshall(int V, vector<vector<long long>>& graph)
{
    for (int v = 1; v <= V; v++)
        for (int from = 1; from <= V; from++)
            for (int to = 1; to <= V; to++)
            {
                if (v == from || v == to)
                    continue;
                if (graph[from][v] == LLONG_MAX || graph[v][to] == LLONG_MAX)
                    continue;
                graph[from][to] = min(graph[from][to], graph[from][v] + graph[v][to]);
            }

}