백준 1916번 최소비용 구하기 문제 풀이

문제 설명

• 시작 도시에서 도착 도시까지 최소 비용 구하는 문제 (버스를 타고 움직인다)

• 도시의 개수 N(1 ≤ N ≤ 1,000)
• 버스 노선의 개수 M(1 ≤ M ≤ 100,000)
• 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수
• 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

문제를 보고 든 생각

1. 도시의 개수가 1000개 밖에 되지 않는다.
2. 버스 비용이 양수.
3. 시작과 도착이 정해져있다.
4. 1:n의 최단경로다.
5. 다익스트라로 풀어야겠다.

간단한 풀이 설명

1. 인접 리스트를 사용했다. (vector<strt> v)
2. 우선순위 큐를 사용했다.
3. 우선순위 큐에는 다음 가야할 정점의 정보와 그곳 까지의 비용을 담았다. (구조체 사용)
4. 거리 정보를 담을 dist 배열을 사용했다.
5. 우선 순위 큐가 빌 때 까지 반복문을 돌았다.

코드

#include <iostream>
#include <queue>
#include <vector>

#define MAX_N 1001

using namespace std;

struct strt{
  int v;
  int cost;
  
  bool operator<(const strt& st)const{
    return cost < st.cost;
  }
  bool operator>(const strt& st)const{
    return cost > st.cost;
  }
};

int visited[MAX_N];
priority_queue<strt, vector<strt>, greater<strt>> pq;
vector<strt> v[MAX_N];
int sCity, dCity;
int N, M;
int dist[MAX_N];

void dijk(){
  while(!pq.empty()){
    strt curr = pq.top(); pq.pop();
    if(visited[curr.v]) continue;
    visited[curr.v] = true;
    dist[curr.v] = curr.cost;

    for(int i=0; i<v[curr.v].size(); ++i){
      strt u = v[curr.v][i];
      if(visited[u.v]) continue;
      pq.push({u.v, u.cost + dist[curr.v]});
    }
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> N >> M;
  for(int i=0; i<M; ++i){
    int s, d, w; cin >> s >> d >> w;
    v[s].push_back({d, w});
  }
  cin >> sCity >> dCity;

  pq.push({sCity, 0});
  dijk();

  cout << dist[dCity];
  return 0;
}