1219번

1219번 - 민식이의 고민

문제 푸는데 엄청 걸렸다 민식이 새끼

이 문제는 정답률이 굉장히 낮은데, 단지 싸이클의 존재여부를 파악하는게 아니라 싸이클이 목적지와 연결이 되어있는지

아닌지를 파악해야 하는 문제여서 그런 것 같다.

근데 로직적으로 다 짜고, 플로이드 알고리즘에서 자기 자신을 true 바꿔주지 않아서.. 한 30번 틀렸다..

### 주의 사항

플로이드 알고리즘을 단지, 연결되어 있는지 여부로 쓸 때랑 모든 쌍의 최단거리를 구할 때 생각하면서 자기자신에 도달 여부를 파악해야겠다.

### 새로 배운 점

SPFA 나 벨만포드를 음수싸이클을 파악할 때 까지 (N-1)까지 돌리면 , 그 때 값들을 이용해서 싸이클에 포함되는 점을 구할 수 있다.

기본적인 로직

1. 플로이드 알고리즘을 통해서 노드끼리 연결되어 있는지를 파악

2. SPFA / 벨만코드 알고리즘을 통해서 최단거리를 구하고, 음수 사이클이 생기는 노드들 파악

3. 음수 사이클이 생기는 노드들을 BFS를 통해 체크

4. 도달 할 수 없는 경우 (플로이드 알고리즘 결과) => gg 출력

   도달 할 수 있는 경우 (플로이드 알고리즘 결과) => 음수 사이클이 생기고, 목적지가 음수 사이클 안에 있는경우 =>Gee 출력

   나머지 => 결과값 출력(SPFA / 벨만코드 알고리즘 결과)

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
const long long INF = 9876543210;
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int n, start, dest, m;
    cin >> n >> start >> dest >> m;
 
    vector<vector<pair<int, int>>> city(n);
    vector<vector<bool>> D(n, vector<bool>(n, false));
 
    while (m--)
    {
        int from, to, edge;
        cin >> from >> to >> edge;
        city[from].push_back({ to,edge });
        D[from][to] = true;
    }
 
    vector<long long> price(n);
    //간선 통합해서 재설정
    for (int i = 0; i < n; i++)
    {
        cin >> price[i];
        D[i][i] = true;
    }
    
 
    //도달 가능 여부 판단 - 플로이드
    for (int k = 0; k < n; k++)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                D[i][j] = D[i][j] || (D[i][k] && D[k][j]);
            }
        }
    }
 
    //SPFA 를 통해서 최소값 구하고, 사이클 확인
    vector<bool> check(n, false);
    vector<long long> dist(n, INF);
    vector<int> cycle(n, 0);
    queue<int> q;
 
    //밑에서 업데이트 되는 정점들 확인하는 BFS 사용할때
    vector<bool> visited(n, false);
    queue<int> bfsQ;
 
    //SPFA 통해서 최단거리 구하기
    bool isCycle = false;
    q.push(start);
    check[start] = true;
    dist[start] = -price[start];
    cycle[start]++;
    int depth = -1;
    while (!q.empty())
    {
        int size = q.size();
        depth++;
        if (depth == n)
        {
            break;
        }
        for (int s = 0; s < size; s++)
        {
            int here = q.front();
            q.pop();
            check[here] = false;
 
            for (int i = 0; i < city[here].size(); i++)
            {
                int there = city[here][i].first;
                long long cost = city[here][i].second - price[there];
 
                if (dist[there] > dist[here] + cost)
                {
                    dist[there] = dist[here] + cost;
 
                    if (!check[there])
                    {
                        cycle[there]++;
                        check[there] = true;
                        q.push(there);
                    }
 
                    if (depth == n - 1)
                    {
                        isCycle = true;
                        bfsQ.push(there);            //BFS 큐에 넣기
                        visited[there] = true;        //BFS 시작값 true
                    }
                }
            }
        }
    }
 
 
    //사이클에 포함되는 정점들로 BFS실행.단방향 간선이므로 정점에 포함되면 모두 사이클에 포함
    while (!bfsQ.empty())
    {
        int now = bfsQ.front();
        bfsQ.pop();
 
        for (int a = 0; a < city[now].size(); a++)
        {
            int next = city[now][a].first;
            if (!visited[next])
            {
                visited[next] = true;
                bfsQ.push(next);
            }
        }
    }
 
    //싸이클이 있던, 없던 도달할 수 없을 때
    if (!D[start][dest])
    {
        cout << "gg\n";
        return 0;
    }
 
    //목적지가 사이클에 연결되어 있는경우
    if (isCycle && visited[dest])
    {
        cout << "Gee\n";
        return 0;
    }
 
    cout << -dist[dest] << "\n";
 
 
    return 0;
}