Algorithm/BOJ
최소비용 구하기 2 - 11779
jhg0406
2020. 3. 12. 03:11
|
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
//11779 - 최소비용 구하기2
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
#define INF 1000000000
int N, M;
vector<vector<pair<int, int>>> adj;
int S, E;
void init()
{
cin >> N >> M;
adj = vector<vector<pair<int, int>>>(N+1);
int x, y, r;
for(int i = 0; i<M; ++i)
{
cin >> x >> y >> r;
adj[x].push_back(make_pair(y, r));
}
cin >> S >> E;
}
void dijkstra(int start)
{
vector<int> dist(N+1, INF);
vector<int> parent(N+1);
dist[start] = 0;
parent[start] = start;
priority_queue<pair<int, int>> pq;
pq.push(make_pair(0, start));
while(!pq.empty())
{
int here = pq.top().second;
int cost = -pq.top().first;
pq.pop();
if(here != start && dist[here] < cost) continue;
for(int i = 0; i<adj[here].size(); ++i)
{
int there = adj[here][i].first;
int c = adj[here][i].second;
if(dist[there] > cost + c)
{
dist[there] = cost + c;
parent[there] = here;
pq.push(make_pair(-(cost+c), there));
}
}
}
cout << dist[E] << "\n";
stack<int> s;
for(int i = E; i != parent[i]; i = parent[i])
s.push(i);
s.push(S);
cout << s.size() << "\n";
while(!s.empty())
cout << s.top() << " ", s.pop();
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
init();
dijkstra(S);
}
|
cs |
https://www.acmicpc.net/problem/11779
11779번: 최소비용 구하기 2
첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시
www.acmicpc.net
최소비용 구하기 2
최단경로 비용과 그 경로를 출력하는 다익스트라 문제입니다.
