BOJ11779_최소비용 구하기2

경로 저장방식 주의!

다익스트라 진행할 때 사용하는 배열과 최종 루트를 저장할 배열 추가

if (d[next.to] <= cur.cost + next.cost) continue; 
= 안넣으니 메모리 초과. 슬라이싱 주의!

#include <iostream>
#include <queue>
#include <vector>
#define INF int(1e9)

using namespace std;

struct Edge {
  int to;
  int cost;
};


struct cmp {
  bool operator() (Edge a, Edge b) {
    if (a.cost >= b.cost) return false;
    else return true;
  }
};

int n, m;
vector<Edge> graph[1005];   // 버스 정보
vector<int> t_route;
int route[1005];
int d[1005];                // 출발 지점에서 각 지점까지의 거리

void dijkstra(int s) {
  priority_queue <Edge, vector<Edge>, cmp> pq;
  pq.push({s, 0});
  d[s] = 0;

  int i = 0;
  while(!pq.empty()) {
    Edge cur = pq.top();
    pq.pop();

    // cout << d[cur.to] << cur.cost << endl;
    if (d[cur.to] < cur.cost) continue;
    for (int i = 0; i < graph[cur.to].size(); i++) {
      Edge next = graph[cur.to][i];
      if (d[next.to] <= cur.cost + next.cost) continue;

      d[next.to] = cur.cost + next.cost;
      route[next.to] = cur.to;
      pq.push({next.to, d[next.to]});
    }
  }
}

int main(void) {
  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

  cin >> n >> m;

  int s, e, c;
  for (int i = 0; i < m ; i++) {
    cin >> s >> e >> c;
    graph[s].push_back({e, c});
  }

  cin >> s >> e;

  for (int i = 1; i <= n; i++) {
    d[i] = INF;
  }

  dijkstra(s);

  int temp = e;
  while (temp) {
    t_route.push_back(temp);
    temp = route[temp];
  }

  cout << d[e] << endl;
  cout << t_route.size() << endl;
  for (int i = t_route.size() - 1; i >= 0; i--) cout << t_route[i] << " ";
  cout << endl;
}