#include <iostream>
using namespace std;
typedef struct _edges
{
    int from;
    int to;
    int cost;
} Edges;
#define INF 987654321
long long aa[1001];
//Edges edges[10000];

int main(void)
{
    int count;
    cin >> count;

    for (int i = 0; i < count; i++)
    {
        int n, m, w;
        int idx = 0;
        Edges edges[10000];

        cin >> n >> m >> w;
        for (int j = 0; j < m; j++)
        {
            int s, e, t;
            cin >> s >> e >> t;
            edges[idx].from = s;
            edges[idx].to = e;
            edges[idx].cost = t;
            idx++;
            edges[idx].from = e;
            edges[idx].to = s;
            edges[idx].cost = t;
            idx++;
        }
        for (int j = 0; j < w; j++)
        {
            int s, e, t;
            cin >> s >> e >> t;
            edges[idx].from = s;
            edges[idx].to = e;
            edges[idx].cost = -t;
            // cout << -t;
            idx++;
        }
        int flag = 0;
        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < idx; k++)
            {
                if ( aa[edges[k].to] > aa[edges[k].from] + edges[k].cost)
                {
                    aa[edges[k].to] = aa[edges[k].from] + edges[k].cost;
                    if (j == n - 1)
                        flag = 1;
                }
            }
        }
        if (flag == 1)
            cout << "YES";
        else
            cout << "NO";
        cout << "\n";
    }
    return 0;
}

https://www.acmicpc.net/board/view/72995

벨만포드 알고리즘과 관련한 문제 여서 풀어봤는데 아직까지 익숙하지 않은 것 같다.

문제 설명

• 간선은 두 종류가 있다.
  도로 : 양방향으로 이동하는 데에 걸리는 시간이므로 T >= 0 이다.
  웜홀 : 단방향으로, 줄어드는 시간으로 T<=0 으로 생각할 수 있다.

이때 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능하면 YES , 불가능하다면 NO를 출력하는 것 => 그래프 내에서 음수 사이클이 존재하면 YES , 존재하지 않으면 NO 를 출력한다.

문제 해결 방법

가중치가 음수인 경우가 존재하므로, 벨만 포드 알고리즘을 적용해야 한다.
벨만포드 알고리즘은 노드가 n 개 존재할 때 최단 경로의 간선이 많아야 n-1 개 이므로, n-1번만 간선을 업데이트 하는 과정을 거치면 최단 경로를 구할 수 있다.
하지만 음수 사이클이 존재할 경우, 한번 더 업데이트를 하여 n번 돌리게 될때와 n-1 번 돌릴 때의 최단 경로가 다른 지점이 존재하게 된다. 이 경우를 감지하였을 때가 음수 사이클이라고 칭하면 된다.

문제 의문점

• 어떻게 시작 정점을 정하느냐 ?
  문제에서는 시작 정점을 명시하지 않았다. 특정 시작 정점이 없으므로, 그래프 내에서 어떤 정점이든 음수 사이클이 존재하면 , YES 라고 출력을 하면 된다.

https://www.acmicpc.net/board/view/72995
나는 이걸 참고하여서 코드 1처럼 풀어보았다. 따라서 시작 정점을 정의하지 않고, INF 는 그 정점을 방문한 것이 아닌 , V까지의 최단 거리가 INF라는 것으로 인식하게 끔 만들었다.

코드 1
INF = 2000000000
모든 dist[v] = INF
N-1번 반복:
모든 v에 대해:
모든 간선에 대해 최단거리 갱신
모든 v에 대해:
모든 간선에 대해 최단거리 갱신
갱신이 한 번이라도 일어났으면 true

• 코드 1 : INF 가 방문했다의 여부가 아닌 ,거리가 INF 라고 해석.

• 코드 2처럼 구현
  INF 의 의미가 그 정점을 방문한 것으로 해석. 시작 정점으로써 도달할수없는 음수 사이클을 못 찾는다. 따라서 시작점을 하나로 잡을 수 없다. 모든 정점에서 동시에 시작할 수 있다! 하지만 시작정점을 명시하고 싶다면 n+1 번째 가짜 정점을 만들어서 모든 정점으로 가중치 0 의 간선을 긋고, 시작 정점을 N+1 로 잡으면 된다.

• 만약 각 정점마다 벨만포드를 돌리면 시간 초과가 난다. O ( N N M)