반응형
✏️ 문제 링크
https://www.acmicpc.net/problem/1753
✏️ 문제 설명 (더보기 클릭 👆🏻)
✏️ 문제 풀이
이전 게시글 참고! 🦄
2021.09.15 - [Algorithm 🧠/알고리듬(thm) 공부 🌱] - [백준] 1916: 최소비용 구하기/ 다익스트라 / C++ ⭐
✏️ 문제 코드
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int, int>;
#define MAX 20001
#define INF 987654321
vector<pii> vec[MAX];
vector<int> dist(MAX, INF);
void dijkstra(int start){
dist[start]=0;
priority_queue<pii> pq; pq.push({0, start});
while(!pq.empty()){
pii t=pq.top(); pq.pop();
int v=t.second; int w=t.first * -1;
if(dist[v]<w) continue;
for(int i=0; i<vec[v].size(); i++){
int nxt=vec[v][i].first;
int nxt_dist=vec[v][i].second + w;
if(nxt_dist<dist[nxt]){
dist[nxt]=nxt_dist;
pq.push({nxt_dist*-1, nxt});
}
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int V, E; cin>>V>>E;
int start; cin>>start;
while(E--){
int u,v,w; cin>>u>>v>>w;
vec[u].push_back({v, w});
}
dijkstra(start);
for(int i=1; i<=V;i++){
if(dist[i]!=INF) cout<<dist[i];
else cout<<"INF";
cout<<"\n";
}
return 0;
}
⭐ if feedback and question : comment please⭐
반응형
'Algorithm 💫 > Problem Solving' 카테고리의 다른 글
[백준] 1446번: 지름길 / C++ (0) | 2021.09.27 |
---|---|
[백준] 1504번: 특정한 최단 경로 / C++ (0) | 2021.09.24 |
[백준] 12851번: 숨바꼭질2 / C++ (0) | 2021.09.17 |
[백준] 14226번: 이모티콘 / C++ (0) | 2021.09.17 |
[백준] 13549번: 숨바꼭질3 / C++ (0) | 2021.09.17 |
댓글