반응형
728x170
어렵다.
다익스트라를 배웠지만
코딩테스트에서 다시 쓰니까 어렵다
https://www.acmicpc.net/problem/1753
#맞은 풀이
#include <iostream>
#include <climits>
#include <queue>
#include <vector>
#include <functional>
#define INF INT_MAX
using namespace std;
int V,E,start;
//벡터를 원소로 가지는 배열 ->
vector <pair<int,int>> adj[20001]; // 인접행렬 from,(weight,to)
//-> adj[1] = {3,5} 의 의미 1번 정점에서 5번으로 가는 가중치 3
//이런 그래프에서 최단거리 => 다익스트라 테이블
int table[20001];
//최소 간선을 위한 minHeap {거리, 정점 번호} -> 일반적으로 first를 기준으로 오름차순으로 정렬함.
/*
void dijkstra(){
prority_queue <pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> minHeap;
table[st] = 0;
minHeap.push({table[st], st});
}
*/
int main(){
cin >> V >> E >> start;
//테이블 초기화 최댓값 INF로
fill(table, table+V+1, INF); //V개만 초기화하면 됨 사실
//E개의 간선 정보 업데이트 -> adj에
for(int i = 0; i<E; i++){
int from, to, weight;
cin >> from >> to >> weight;
adj[from].push_back({weight, to}); // 해당 정점에서 어디로 가느냐
}
//최소힙 생성
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > minHeap;
table[start] = 0;
minHeap.push({table[start], start}); //거리, 정점
while(!minHeap.empty()){
auto cur = minHeap.top();
minHeap.pop();
//거리, to를 뽑음
int dist = cur.first;
int idx = cur.second;
//해당 정점에 대한 최단거리 테이블의 정보와 비교해서 조사해야하는지 확인
if(table[idx] < dist) continue;
//그렇다면 해당 정점이 갈 수 있는 곳을 알아봄
//adj[from] = {weight, to}
for(auto next : adj[idx]){
int cost = next.first; //해당 정점에 가는데 드는 가중치
int nidx = next.second; //갈 수 있는 정점
//해당 정점이 갈 수 있는 거리 중 table에 있는 것보다 작다면 업데이트
if(table[nidx] > dist + cost){
table[nidx] = dist+cost;
minHeap.push({table[nidx], nidx});
}
}
}
//출력
for(int i = 1; i <= V; i++){
if(table[i] == INF) cout << "INF\n";
else cout << table[i] << "\n";
}
}
이와 비슷한 문제를 조금 더 풀어보면서 복습해야겠다.
728x90
반응형
그리드형
'문제풀이(Problem Solving)' 카테고리의 다른 글
백준, BOJ, 3190번, 뱀 : C++ [CPP] (0) | 2021.12.08 |
---|---|
백준, BOJ, 1707번, 이분 그래프 : C++ [CPP] ★ (0) | 2021.12.07 |
백준, BOJ, 16637번, 괄호추가하기 : C++ [CPP] (0) | 2021.12.06 |
백준, BOJ, 1543번, 문서 검색 : C++ [CPP] (0) | 2021.12.05 |
백준, BOJ, 2503번, 숫자야구 : C++ [CPP] (0) | 2021.12.05 |