11779 - 최소비용구하기2

첫번째 시도

		if (cur_dist > dist[cur_node])continue;
        // while문 안에서는 결론이 났지만 이미 queue에 들어와 있는 원소들 때문에 시간 초과

첫번째 시도에는 저 코드를 쓰지 않았다 위 코드를 추가해야 시간초과가 안난다.

두번재 시도

#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
using namespace std;

#define INF 2000000000;
			
vector<pair<int, int>>v[1001];
vector<int> last;
int N, M;
int a, b, w;
int Start, End;
int ans;
int dist[1001];
int parent[1001];

void dijkstra() {
	priority_queue<pair<int, int>> pq;
	pq.push({ -0,Start });
	dist[Start] = 0;
	while (!pq.empty()) {
		int cur_dist = -pq.top().first;
		int cur_node = pq.top().second;
		pq.pop();

		if (cur_dist > dist[cur_node])continue;// while문 안에서는 결론이 났지만 이미 queue에 들어와 있는 원소들 때문에 시간 초과
		for (int i = 0; i < v[cur_node].size(); i++) {
			int next_dist = cur_dist + v[cur_node][i].second;
			int next_node = v[cur_node][i].first;
			if (dist[next_node] > next_dist) {
				parent[next_node] = cur_node;
				dist[next_node] = next_dist;
				pq.push({ -next_dist, next_node });
			}
		}
	}
	
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;
	for (int i = 1; i <= N; i++) { dist[i] = INF; }
	
	
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> w;
		v[a].push_back({ b,w });
	}

	cin >> Start >> End;

	dijkstra();

	int tmp = End;
	last.push_back(End);
	int val = parent[End];
	while (val) {
		last.push_back(val);
		val = parent[val];
	}
	cout << dist[End] << '\n';
	cout << last.size()<<'\n';
	int S = last.size() - 1;
	for (int i = S; i >=0 ; i--) {
		cout << last[i] << " ";
	}
	return 0;
}