8-P 문제 질문

작성한 질문수 28

1

안녕하세요 명운님 ㅎㅎ

양의 사이클이 있고 도착하거나 도착하지 않는 경우의 수에 대한 로직이 꼬여서 그렇습니다.

    if (q.size() && dist[e] != INF) cout << "Gee" << '\n';
    else {
        if (dist[e] != INF) cout << -dist[e] << '\n';
        else cout << "gg" << '\n';
    }

이로직은 얼핏보면 맞아 보이지만 이경우를 처리하지 못합니다.

양의 사이클은 존재 but, 이 사이클이 도착지점으로까지 연결되지 않을 때도 Gee를 출려할 수 있습니다.

그렇기 때문에 해당 부분을 처리해주어야 합니다. (BFS로)

또한

dist의 범위.

즉, n=100이고 100개의 도시 전체가 하나의 큰 사이클을 이룬다고 치면 100*100*1,000,000이 될 수도 있어 int범위를 넘어가게 될 수 있기 때문에 dist는 long long으로 선언해주어야 합니다.

제가 좀 다듬어봤는데요 ㅎㅎ

참고부탁드립니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; 
const ll INF = (int)1e18; 
ll V, E, s, e, a, b, c, tmp[104], dist[104], visited[104];
vector<pair<ll, ll>> adj[104];
queue<ll> q;

void bellman() {
    fill(dist, dist + 104, INF);
    dist[s] = tmp[s];
    for (int i = 0; i < V; i++) {
        for (int here = 0; here < V; here++) {
            for (auto there : adj[here]) {
                ll to = there.first;
                ll d = there.second;
                if (dist[here] != INF && dist[to] > dist[here] + d + tmp[to]) {
                    if (i == V - 1) q.push(to);
                    dist[to] = dist[here] + d + tmp[to];
                } 
            }
        }
    }
}

int main() { 
    cin >> V >> s >> e >> E;
    for (int i = 0; i < E; i++) {
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
    }
    for (int i = 0; i < V; i++) {
        int n;
        cin >> n; tmp[i] = -n;
    }
    bellman();
    bool ok = 0; 
    
    while(q.size()){
        int here = q.front(); q.pop();
        for(pair<int, int> there : adj[here]){
            if(there.first == e){
                ok = 1; break;
            }
            if(!visited[there.first]){
                visited[there.first] = 1;
                q.push(there.first);
            }
        }
        if(ok) break;
    }

    if(dist[e] == INF)puts("gg");
    else if(ok)puts("Gee");
    else printf("%lld\n", -dist[e]); 
    return 0;
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.