[7일차] 그래프2 B - 1753: 최단경로

골드 Ⅴ

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 987654321
using namespace std;

struct NodeInfo {
	int node;
	int weightOrshdis;
};

struct compare {
	bool operator()(const NodeInfo& NodeInfo1, const NodeInfo& NodeInfo2) {
		return NodeInfo1.weightOrshdis > NodeInfo2.weightOrshdis;
	}
};

//그래프 연결관계 저장 -> nodeNum, weight
vector<NodeInfo> adjList[20001];//노드 넘버와 그 노드까지 가는데 드는 weight 저장 필요
//nodeNum, shdis -> shdis로 정렬할거라 둘다 넣어줘야함
priority_queue<NodeInfo, vector<NodeInfo>, compare> toStart;
//이색 왜필요하지 일단 필요할거같으니까 써놓고 필요없으면 지우기
int shdis[20001];//각 노드들의 최단 거리! 저장 최단 경로가 아니라
bool visit[20001] = { 0, };//false로 초기화

int V, E, K;
int main() {
	scanf("%d%d%d", &V, &E, &K);
	
	//shdis inf로 초기화
	for (int i = 1; i <= V; i++) {
		if (i == K) shdis[i] = 0;
		else shdis[i] = INF;
	}
	toStart.push({ K, 0 });//시작점 넣어주기

	//연결 정보 받아주기
	int u, v, w;
	while (E--) {
		scanf("%d%d%d", &u, &v, &w);
		//노드 u와 연결된 얘들 i 중에
		bool isDup = false;
		for (int i = 0; i < adjList[u].size(); i++) {
			int connectedNode = adjList[u][i].node;
			int oldweight = adjList[u][i].weightOrshdis;
			//연결된 노드에 이미 v가 있다면 w 업데이트 
			if (connectedNode == v) {
				printf("중복이네 %d -> %d\n", oldweight, w);
				adjList[u][i].weightOrshdis = min(oldweight, w);
				printf("%d됨\n", adjList[u][i].weightOrshdis);
				isDup = true;
			}
		}
		//중복 안됐다면 업데이트
		if (!isDup) adjList[u].push_back({ v, w });
	}

	//인접리스트 출력
	for (int i = 1; i <= V; i++) {
		printf("노드 %d: \n", i);
		for (int j = 0; j < adjList[i].size(); j++) {
			printf("(to %d -> weight: %d)\n", adjList[i][j].node, adjList[i][j].weightOrshdis);
		}
	}//졸라 잘 들어감 출력이 이해하기 쉽네 굳굳

	//다익스트라 ㄱㄱ
	while (!toStart.empty()) {
		
		int startNode = toStart.top().node;
		toStart.pop();
		visit[startNode] = true;
		printf("노드 %d에서 시작!\n", startNode);

		//뽑은 startNode와 연결된 node 업데이트 해주기
		for (int i = 0; i < adjList[startNode].size(); i++) {
			int connectedNode = adjList[startNode][i].node;
			int weight = adjList[startNode][i].weightOrshdis;
			printf("to -> %d : weight : %d\n", connectedNode, weight);

			//방문한 노드면 스킵
			if (visit[connectedNode] == true) continue;

			//연결된 node의 현재 shdis보다 startNode dis + weight가 더 작다면 update
			if (shdis[connectedNode] > shdis[startNode] + weight) {
				//shdis 업데이트
				shdis[connectedNode] = shdis[startNode] + weight;
				//tostart에 넣어주기 (to start에 이미 들어간 경우는 중복으로 들어가지만)
				//(shdis가 더 작게 들어가므로 update해주는 효과를 냄)
				//-> 더 큰 값으로 있던 건 무시됨
				toStart.push({ connectedNode, shdis[connectedNode] });
			}
		}
	}

	for (int i = 1; i <= V; i++) {
		if (shdis[i] == INF) printf("INF\n");
		else printf("%d\n", shdis[i]);
	}
}

 

다익스트라 + 다중간선이 있을 경우 더 작은값으로 치환

 

인 줄 알았는데 왜 강사님 코드 보니까 치환 안하지

머지

머임?

 

그리고... toStart 업데이트 안해주는거 내가 생각한게 맞는지 모르겠음 진짜 확인해야될거같음