글 읽기 - 1219번 요청있습니다.

kywho0915 4년 전 0

아래의 코드로는 자가순환해서 Gee가 되는 경우 아래의 예시가 맞지 않는데 맞았습니다로 뜨는 것 같습니다.

( 문제에서 예시4번의 경우 자가 순환해서 Gee가 나오는 경우를 보고 도착하면 끝이 아닌 도착해도 순환해서 돈의 증가가 가능하면 Gee를 출력하는 것으로 이해했습니다.)

예시

입력

1 0 0 1

0 0 6

출력

Gee

틀린출력

따라서 위의 예시를 데이터에 추가해야 된다고 생각합니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct P {
   int u, v, w;
};
using lint = long long;

const lint INF = 1LL << 60;
const lint mINF = -(1LL << 60);
int N, S, E, M;
int city[101];
lint dist[101];
vector<P> edge;

bool vis[101];
void init() {
   for (int i = 0; i < N; i++)
      dist[i] = mINF;
   dist[S] = city[S];
}

void input() {
   cin >> N >> S >> E >> M;
   for (int i = 0; i < M; i++) {
      int u, v, w;
      cin >> u >> v >> w;
      edge.push_back({ u,v,-w });
   }
   for (int i = 0; i < N; i++) {
      cin >> city[i];
   }
   init();
}

void bellmanFord() {
   for (int i = 0; i < N+M-2; i++) {
      for (auto edg : edge) {
         int u = edg.u, v = edg.v, w = edg.w;
         if (dist[u] == mINF) continue;
         else if (dist[u] == INF) dist[v] = INF;
         else if (dist[v] < dist[u] + w + city[v]) {
            dist[v] = dist[u] + w + city[v];
            if (i >= N - 1) dist[v] = INF;
         }
      }
   }
}

void proc() {
   bellmanFord();
   if (dist[E] == mINF)
      printf("gg\n");
   else if (dist[E] == INF)
      printf("Gee\n");
   else printf("%lld\n", dist[E]);
}

int main() {
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr); cout.tie(nullptr);
   input();
   proc();
   return 0;
}

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

문제

문제

출처

ICPC

1219번 요청있습니다.

kywho0915 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말