티스토리 뷰
https://www.acmicpc.net/problem/5972
5972번: 택배 배송
문제 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현��
www.acmicpc.net
백준 소스코드 [C++] 5972 택배 배송
#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
using namespace std;
int v, e, start,desti, s, d, weight;
vector <pair<int, int>> adj[50000];
vector<int> dijkstra(int src) {
priority_queue <pair<int, int> > pq;
vector<int> dist(v, INT_MAX);
dist[src] = 0;
pq.push({ 0,src });
while (pq.empty() != true) {
int cost = -pq.top().first;
int here = pq.top().second;
pq.pop();
if (dist[here] < cost) continue;
for (int i = 0;i < (int)adj[here].size();i++) {
int there = adj[here][i].first;
int nextdist = cost + adj[here][i].second;
if (dist[there] > nextdist) {
dist[there] = nextdist;
pq.push({ -nextdist,there });
}
}
}
return dist;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> v>> e;
for (int i = 0;i < e;i++) {
cin >> s >> d >> weight;
adj[s-1].push_back(make_pair(d-1, weight));
adj[d - 1].push_back(make_pair(s - 1, weight));
}
cout << dijkstra(0)[v - 1];
return 0;
}
'백준' 카테고리의 다른 글
백준 소스코드 [C++] 2164 카드 2 (0) | 2020.08.27 |
---|---|
백준 소스코드 [C++] 1978 소수 찾기 (0) | 2020.08.27 |
백준 소스코드 [C++] 1238 파티 (0) | 2020.08.26 |
백준 소스코드 [C++] 1916 최소비용 구하기 (0) | 2020.08.26 |
백준 소스코드 [C++] 1753 최단경로 (0) | 2020.08.26 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
TAG
- 벨만포드 시간복잡도
- 에드몬드 카프 알고리즘
- observeOn
- CompositionalLayout
- 네트워크 플로우
- 강한 순환 참조
- 컴퓨터 추상화
- 부스트캠프 6기
- 최단경로 문제
- WWDC16
- rxswift
- mach-o
- WWDC17
- IOS
- HIG
- 최단경로문제
- 포드 풀커슨 알고리즘
- 다익스트라 시간복잡도
- 벨만포드 알고리즘
- WWDC19
- 코딩대회
- 네트워크 유량
- CPU와 Memory
- 최대 매칭
- State Restoration
- 최단경로 알고리즘
- MeTal
- WWDC21
- Testable
- test coverage
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
글 보관함