https://www.acmicpc.net/problem/1916
1916번: 최소비용 구하기
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그
www.acmicpc.net
이 문제는 다익스트라 알고리즘을 그대로 사용하면 풀 수 있는 문제이다. 자세한 풀이 과정은 이전에 내가 올려놓은
https://fastgamedev.tistory.com/49
백준 1753
이 문제의 경우 나에게 여러가지 에러를 보여줌으로 여러가지 함수를 사용할 때 주의 할점을 알려줬다. 일단 이 문제의 코드는 이렇게 된다 #include #include #include #define INT_MAX 2147483647 using namespace
fastgamedev.tistory.com
이 글의 문제와 똑같이 풀고나서 해당 도착지의 값만 출력해주는 문제라 매우 쉬웠다.
#include<iostream>
#include<queue>
#include<vector>
#define INT_MAX 2147483647
using namespace std;
vector<pair<int, int>> djikstraPQ [1001];
vector <int> distanceV(1001);
void dijkstra(int start) {
priority_queue < pair<int, int>, vector < pair<int, int>>, greater<pair<int, int>>> pq;// front는 cost second 는 index
pq.push({ 0, start });
distanceV[start] = 0;
while (!pq.empty()) {
int costTo = pq.top().first;
int toIdx = pq.top().second;
pq.pop();
if (distanceV[toIdx] < costTo) {
continue;
}
for (int i = 0; i < (int)djikstraPQ[toIdx].size(); i++) {
// 나랑 연결되어 있는애가 Second 비용이 front
int cost = djikstraPQ[toIdx][i].second + costTo;
if (cost < distanceV[djikstraPQ[toIdx][i].first]) {
distanceV[djikstraPQ[toIdx][i].first] = cost;
pq.push({ cost, djikstraPQ[toIdx][i].first });
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M, start, arrive;
cin >> N >> M;
int from, to, cost;
for (int i = 0; i < M; i++) {
cin >> from >> to >> cost;
djikstraPQ[from].push_back({ to,cost });
}
cin >> start >> arrive;
distanceV.assign(1001,INT_MAX);
dijkstra(start);
cout << distanceV[arrive];
}