문제 URL : https://www.acmicpc.net/problem/17835
17835번: 면접보는 승범이네
첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐
www.acmicpc.net
문제 접근법:
다익스트라를 이용할줄 안다면 문제 접근하는건 크게어렵지 않습니다.
면접장까지의 거리가 가장 먼도시와 그거리를 구하기때문에
순방향으로 그래프를 그리셨다면 답은 구해질수 있을지 언정 시간이 굉장히 오래 걸립니다.
일일이 한집에서 면접장까지 구하기때문에 다익스트라를 여러번 돌려야하기 때문에
그렇다면 반대로 면접장까지 가는 거리를 구하는거니 면접장 출발해서 도시들을 가는 거리를 구한다면
그도시에서 면접장 까지의 거리가 나오고 역방향으로 만든다면 여러번 돌릴 필요가없겟죠?
그치만 아직까지는 부족한것들이 더 있습니다. 면접장들은 여러개이니 이것을 한 집합으로 보고
그 면접장들에서 한꺼번에 출발하여 가장 가까운 도시들과의 거리를 구하고 그도시들중에서 가장 거리가 먼
거리를 구한다면 시간은 충분히 줄여줄수 있습니다.
그러나.. 이렇게 까지 풀고 저는 여러번 시간초과가 났는데
한가지 더필요한것은 내가 현재지점에서 지나온 비용들의 합과 dist에 최단거리로 저장해두었던 비용을 비교하여
만약 dist에 저장했던 비용보다 크다면 그다음 지나간 거리는 구할필요도 없이 먼거리기에 계산을 할필요가
없다는것을 알아야 시간을 빠르게 동작할수 있습니다.
문제핵심은 다익스트라를 이용해도 최대한 가지치기를 많이 하라는 문제 였던것같습니다.
|
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
74
75
76
77
78
79
80
81
82
|
#include <iostream>
#include<cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;
struct dij{
ll cur, sumcost;
dij(ll cur, ll sumcost) :cur(cur), sumcost(sumcost){}
};
struct cmp{
bool operator()(dij &a, dij &b){
if (a.sumcost > b.sumcost)
return true;
return false;
}
};
ll n, m, k;
ll dist[100001];
vector<dij> v[100001];
priority_queue<dij, vector<dij>, cmp> pq;
void input()
{
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
dist[i] = 1e+15;
for (int i = 0; i < m; i++)
{
ll a, b, c;
cin >> a >> b >> c;
v[b].push_back({a,c});//역방향그래프로 시작을해야 해당면접장까지 갈수있는 방법을 빠르게 구할수있음
}
for (int i = 0; i < k; i++)
{
ll a;
cin >> a;
dist[a] = 0;//면접장들을 집합이라고생각할때 가장 가까운 면접장을 가기위해
pq.push({ a, 0 });//면접장들을 한꺼번에 pq에 넣어서 돌림
}
}
void dijkstra(){
while (!pq.empty())
{
ll cur = pq.top().cur;
ll sumcost = pq.top().sumcost;
pq.pop();
if (dist[cur] < sumcost)//지금까지 더한 비용이 현재보다 더 클경우 다음비용은 보지않아도 저장되어있는 dist값보다 클수밖에없음
continue;//이거 빼주면 시간초과
for (int i = 0; i < v[cur].size(); i++)
{
ll next = v[cur][i].cur;
ll cost = v[cur][i].sumcost + sumcost;
if (dist[next]>cost)
{
pq.push({ next, cost });
dist[next] = cost;
}
}
}
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
dijkstra();
ll Max = 0, idx = 0;
for (int i = 1; i <= n; i++)//
{
if (dist[i] > Max)
{
Max = dist[i];
idx = i;
}
}
cout << idx << "\n";
cout << Max << "\n";
}
|
cs |
궁금한점은 모르는 점이 있다면 언제나 댓글을 이용하여 질문을 남겨주시기 바랍니다.
'백준' 카테고리의 다른 글
| 백준 17834 사자와 토끼 (0) | 2020.07.26 |
|---|---|
| 백준 1707 이분그래프 (0) | 2020.07.26 |
| 백준 2812 크게만들기 (0) | 2020.07.22 |
| 백준 1890 점프 (0) | 2020.07.22 |
| 백준 17830 이진수씨의 하루 일과 (0) | 2020.07.22 |
