Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
복실
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int solution(int N, vector<vector<int> > road, int K) {
int answer = 0;
int village[51][51];
int INF = 10000 * 50;
bool visited[51];
int D[51];
for (int i = 1; i <= N; i++) {
D[i] = INF;
visited[i] = false;
for (int j = 1; j <= N; j++) {
if (i == j) village[i][j] = 0;
else village[i][j] = INF;
}
}
D[1] = 0;
visited[1] = true;
for (int i = 0; i < road.size(); i++) {
village[road[i][0]][road[i][1]] = village[road[i][0]][road[i][1]] > road[i][2] ? road[i][2] : village[road[i][0]][road[i][1]];
village[road[i][1]][road[i][0]] = village[road[i][1]][road[i][0]] > road[i][2] ? road[i][2] : village[road[i][1]][road[i][0]];
}
priority_queue<pair<int, int> > pq; // <-거리, 노드>
// dijkstra algorithm
for (int i = 1; i <= N; i++) {
D[i] = village[1][i];
pq.push(make_pair(-D[i], i));
}
while (!pq.empty()) {
int cost = -pq.top().first;
int currentNode = pq.top().second;
pq.pop();
// if (D[currentNode] < cost) continue;
// 인접 정점 모두 검사
for (int i = 1; i <= N; i++) {
if (D[currentNode] + village[currentNode][i] < D[i]) {
D[i] = D[currentNode] + village[currentNode][i];
pq.push(make_pair(-D[i], i));
}
}
}
for (int i = 1; i <= N; i++) {
if (D[i] <= K) ++answer;
// cout << D[i] << ", ";
}
return answer;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment