[백준] 11657번 타임머신 c++

https://www.acmicpc.net/problem/11657

11657번: 타임머신

 

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. 

출력

만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

 

접근방식 및 고려사항

- 벨만포드 알고리즘을 연습할 수 있는 기본문제이다.

- 도시개수, 노선개수, 노선정보로 인해 나올 수 있는 dist의 최대값MAX(300만<= MAX <= -300만) 고려해야 한다.

- 만약 INF를 int 형의 최대값인 21억으로 INF를 잡았다면 21억의 어떤 노드 가중치가 INF인 경우 오류가 발생한다.

- 만약 dist를 int으로 선언한다면 음의 싸이클이 돌아가는데 -21억을 넘어가면 문제된다.

#include <iostream>
#include <vector>
#define INF 100000000000
#define VMAX 501
#define EMAX 6001

using namespace std;

vector<pair<pair<int,int>, int>> a;
int n,e; 
long long dist[VMAX];
bool path_ok=true;

void bellman_ford(){
  for(int i=1; i<=n; i++) dist[i] = INF;

  dist[1] = 0;

  for(int i=1; i<=n-1; i++){
    for(int j=0; j<e; j++){
      int x = a[j].first.first;
      int y = a[j].first.second;
      int w = a[j].second;
      if(dist[x] == INF) continue;
      if(dist[y] > dist[x] + w){
        dist[y] = dist[x] + w;
      }
    }
  }
  for(int j=0; j<e; j++){
      int x = a[j].first.first;
      int y = a[j].first.second;
      int w = a[j].second;
      if(dist[x] == INF) continue;
      if(dist[y] > dist[x] + w){
        path_ok=false;
      }
    }

}
int main(){
  cin >> n >> e;
  for(int x,y,w,i=0; i<e; i++){
    scanf("%d %d %d", &x, &y, &w);
    a.push_back({{x,y},w});
  }
  bellman_ford();
  if(path_ok){
    for(int i=2; i<=n; i++){
      if(dist[i]!=INF) printf("%lld\n", dist[i]);
      else printf("-1\n");
    }
  }else{
    printf("-1\n");
  }
}

느낀점

- 알고리즘에도 집중해야 하지만 세세한 문제조건들을 잘 따지면서 문제롤 꼼꼼하게 풀겠다면 마음으로 문제를 풀어야겠다.