글 읽기 - 16%에서 WA를 받는데 어느 부분이 잘못되었나요..?

wondy1128 6년 전 0

코드에 설명은 주석으로 작성해 두었습니다.

제가 벨만포드 알고리즘을 잘못이해한 것인가요...??

다른 질문을 보고

4 0 3 4
0 1 0
1 2 0
2 1 0
0 3 10
10 10 10 10

인 경우에 답이 10이 나와야 하는 것인가요..?

Gee 가 나와야 하는 것인가요?

우선사항이

1. 도착점에 도착하기 dist[e]

2. 도착할 수 있다면, 음의 사이클 존재여부 Gee

3. 도착할 수 없음. gg

인가요??

#include<cstdio>
#include<vector>
#include<utility>
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;
const LL INF = 999999999999999999;
VLL city_plus; // 정점에서의 +얻는 돈.
VPLL path_minus[111]; // 간선 -이동하며 손실하는 돈.
VLL dist; // 이동하며 지점마다 돈을 저장하기 위한 변수
int main(){
    // input
    int n,s,e,m;
    scanf("%d%d%d%d",&n,&s,&e,&m);
    city_plus = VLL(n+1, 0);
    dist = VLL(n+1, 0);
    for(int i = 0 ; i < m ; i++){
        LL u, v, cost;
        scanf("%lld%lld%lld", &u, &v, &cost);
        path_minus[u].pb(mp(v,cost));
    }
    for(int i = 0 ; i <= n-1 ; i++) scanf("%lld", &city_plus[i]);
    // input end
    
    // init cost
    for(int i = 0 ; i <= n-1 ; i++) dist[i] = -INF; // 나머지 도시는 -INF
    dist[s] = city_plus[s]; // 시작도시에서 돈을 초깃값으로 잡음
    
    
    // Bellman-Ford iteration 1
    for(int vertex = 0 ; vertex < n-1 ; vertex++){
        for(int here = 0 ; here <= n-1 ; here++){
            for(auto iter = path_minus[here].begin() ; iter != path_minus[here].end() ; iter++){
                PLL p = *iter;
                LL there = p.first;
                LL cost = p.second;
                // dist 값을 갱신
                // dist[here] 가 -INF 인 경우, 
                // -cost + city_plus[there] 가 -INF + a 인 경우가 발생할 수 있으므로
                // 제외시켜야함.
                if(dist[here] != -INF && dist[there] < dist[here] - cost + city_plus[there]){
                    dist[there] = dist[here] - cost + city_plus[there];
                }                
            }
        }
    }
    
    
    // Bellman-Ford iteration 2 ; 음의 사이클 유무 판정.
    for(int here = 0 ; here <= n-1 ; here++){
        for(auto iter = path_minus[here].begin() ; iter != path_minus[here].end() ; iter++){
            PLL p = *iter;
            LL there = p.first;
            LL cost = p.second;
            // 음의 사이클 유무 판정
            if(dist[here] != -INF && dist[there] < dist[here] - cost + city_plus[there]){
                
                // 만약 dist[e] 도착위치 값이 -INF 인 경우에는 gg 인 경우이므로 if문
                if(dist[e]!=-INF){
                	printf("Gee");	
                	return 0;
                }
            }
        }
    }
    // 3
    
    if(dist[e] != -INF){
        printf("%lld", dist[e]);    
    }else{
        printf("gg");
    }    
    return 0;
}
// 16% WA

jsu4838 6년 전 0

저도 현재 도전 중에 16% WA인데,

찾아보니 말씀하신 테스트 케이스의 경우 10이 나오는게 정답인듯 합니다.

음의 사이클이 나왔을 때 그 사이클이 도착지점에 도달 가능한 사이클인지를 판단해야 한다고 합니다.

어떻게 해야할지는 저도 고민중이네요 ㅠ

leehosu01 6년 전 0

그건 사실 floyd 로 하면 d[v][f]!=INF 로 확인 하면 되고 아니면 BFS 로 도달 가능 여부 확인하세요<<endl

dbfldkfdbgml 3년 전 0

4 0 3 4
0 1 0
1 2 0
2 1 0
0 3 10
10 10 10 10

정답은 10입니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

16%에서 WA를 받는데 어느 부분이 잘못되었나요..?

wondy1128 6년 전 0

jsu4838 6년 전 0

leehosu01 6년 전 0

dbfldkfdbgml 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말