[8일차] 그래프2 H - 1854: K번째 최단경로 찾기

플래티넘 Ⅳ

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int n, m, k;

struct NodeInfo {
	int node;
	int weightOrdis;
};

struct compare {
	bool operator()(const NodeInfo& NodeInfo1, const NodeInfo& NodeInfo2) {
		return NodeInfo1.weightOrdis > NodeInfo2.weightOrdis;
	}
};
//visit 필요없음
vector<NodeInfo> adjList[1001];
priority_queue<NodeInfo, vector<NodeInfo>, compare> toStart;
priority_queue<int> dis[1001];
//int shdis[1001] -> 최소값 저장해놓는 곳.. 인데 필요없어짐
//이 문제에서 최소값은.. 필요없다!

int main() {
	scanf("%d%d%d", &n, &m, &k);

	int a, b, c;
	while (m--) {
		scanf("%d%d%d", &a, &b, &c);
		adjList[a].push_back({ b, c });
	}
	toStart.push({ 1, 0 });
	dis[1].push(0);

	//다익스트라 진행
	while (!toStart.empty()) {
		NodeInfo cur = toStart.top();
		toStart.pop();

		//dis 현재값보다 더 큰 얘들 들어온거 무시
		//하면 안되는구나...
		//if (cur.weightOrdis > shdis[cur.node]) continue;
		//더 큰 값들도 다 되게 해야 k번째를 찾을 수 있음.....
		
		//!!!
		//dis[cur.node]의 큐의 모든 값들은
		//이미 toStart에 다 들어가 있다... (cur.node, dis[cur.node][몇번쨰]) 이렇게 다~~

		for (int i = 0; i < adjList[cur.node].size(); i++) {
			int adjNode = adjList[cur.node][i].node;
			int w = adjList[cur.node][i].weightOrdis;

			//달려있는 개수가 k보다 작으면
			if (dis[adjNode].size() < k) {
				//걍 넣기
				dis[adjNode].push(cur.weightOrdis + w);
				toStart.push({ adjNode, cur.weightOrdis + w });
			}//k개수랑 같거나 큰데 현재 값 + w이 더 작으면
			else if (dis[adjNode].top() > cur.weightOrdis + w) {
				//뽑고 넣어
				dis[adjNode].pop();
				dis[adjNode].push(cur.weightOrdis + w);
				toStart.push({ adjNode, cur.weightOrdis + w });
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		if (dis[i].size() < k) printf("-1\n");
		else printf("%d\n", dis[i].top());
	}
}

 

다익스트라 + (그래프 이론) 이란다

 

충격적~~~~~

우선순위큐에 업데이트 안 된 옛날 정보도 들어가는 걸 이용해서

굳이 dis[cur.node]에 있는 큐 모든 값들 + weight 랑 dis[nextNode]의 최대값이랑 비교해서

다~ 넣어주는 과정을 거치지 않고

toStart에서 하나 뽑은 cur 여기에서 cur.weightOrdis 얘가 dis[cur.node]의 큐에 있는 모든 값을이 자동으로 되니까

이걸로 그냥 업데이트 해주면.. 됨.

 

그리고 dis[1].push(0) 해주는거 필요없을 줄 알고 안했는데

안하니까 제출에서는 틀렸습니다 가 뜨더라

생각해보니까 그럴 거 같기도 하다 음 예시를 팍 못들겠는데

이게 사이즈가 0인데 뽑으라고 한다기 보다는 음

문제에 있었던.. i에서 i가 0이랬나 그거랑 관련이 있으려나

생각해보니까 또 예시를 못찾겠는데 잘 모르는거같기도하고

한 번 생각해봐야할듯