문제
마포구에는 모든 대학생이 입사를 희망하는 굴지의 대기업 ㈜승범이네 본사가 자리를 잡고 있다. 승범이는 ㈜승범이네의 사장인데, 일을 못 하는 직원들에게 화가 난 나머지 전 직원을 해고하고 신입사원을 뽑으려 한다. 1차 서류전형이 끝난 뒤 합격자들은 면접을 준비하게 되었다.
면접자들은 서로 다른 N개의 도시에 거주한다. 승범이는 면접자들의 편의를 위해 거주 중인 N개 도시 중 K개의 도시에 면접장을 배치했다. 도시끼리는 단방향 도로로 연결되며, 거리는 서로 다를 수 있다. 어떤 두 도시 사이에는 도로가 없을 수도, 여러 개가 있을 수도 있다. 또한 어떤 도시에서든 적어도 하나의 면접장까지 갈 수 있는 경로가 항상 존재한다.
모든 면접자는 본인의 도시에서 출발하여 가장 가까운 면접장으로 찾아갈 예정이다. 즉, 아래에서 언급되는 '면접장까지의 거리'란 그 도시에서 도달 가능한 가장 가까운 면접장까지의 최단 거리를 뜻한다.
속초 출신 승범이는 지방의 서러움을 알기에 각 도시에서 면접장까지의 거리 중, 그 거리가 가장 먼 도시에서 오는 면접자에게 교통비를 주려고 한다.
승범이를 위해 면접장까지의 거리가 가장 먼 도시와 그 거리를 구해보도록 하자.
입력
첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다.
다음 M개의 줄에 걸쳐 한 줄마다 도시의 번호 U, V(U ≠ V)와 도로의 길이 C(1 ≤ C ≤ 100,000)가 공백을 두고 순서대로 주어진다. 이는 도시 U에서 V로 갈 수 있는 도로가 존재하고, 그 거리가 C라는 뜻이다.
마지막 줄에 면접장이 배치된 도시의 번호 K개가 공백을 두고 주어진다.
출력
첫째 줄에 면접장까지 거리가 가장 먼 도시의 번호를 출력한다. 만약 그런 도시가 여러 곳이면 가장 작은 번호를 출력한다.
둘째 줄에 해당 도시에서 면접장까지의 거리를 출력한다.
예제 입력 1
6 10 2
2 6 2
1 4 1
6 1 5
2 5 1
5 1 4
4 5 6
6 2 3
3 5 1
3 1 1
5 2 2
1 2
예제 출력 1
4
8
예제 입력 2
10 20 5
4 1 18
6 1 7
2 4 1
5 6 18
7 6 10
10 6 9
3 2 4
8 3 10
9 8 15
7 1 12
10 7 1
8 1 3
6 5 19
2 9 10
7 2 4
10 3 20
7 10 14
5 7 12
8 4 10
2 5 8
1 8 4 6 7
예제 출력 2
9
15
문제 정리
문제를 처음 봤을 때 각 정점에서 면접장까지의 거리를 다익스트라로 구현했지만 시간초과가 났다. 각 정점에서 면접장까지의 거리를 반복문으로 통해 구해야하고 N,M의 크기가 크기 때문이다.
-> 반대로 면접장에서 각 정점까지의 거리를 구한다!
사실 생각하기가 너무 어려워서 이렇게 풀 수도 있구나 생각했다. 그렇게 하기 위해서는 입력을 반대로 받아야 한다. a에서 b까지 거리가 c라고 한다면 b에서 a까지의 거리가 c가 되게 해야한다.
(a->면접장 :2 면접장->a :3 일 때 면접장에서 a까지의 거리는 3이지만 우리가 구하고자 하는 값은 2이다)
시간초과가 난 코드
/*각 도시에서 면접장 까지의 거리를 계산한 풀이
시간복잡도는 O(VElgE)가 되며, V와 E가 10^5 단위기 때문에
제한 시간 내로 풀리지 않음.*/
using namespace std;
vector <pair<int,int>> adj[100002];
int dist[100002];
int place[100002];
const int INF = 1e9;
int n,m,k;
int a,b,cost;
int dijkstra(int st, int en)
{
fill(dist,dist+n+1,INF);
dist[st] = 0;
priority_queue < pair<int,int> ,vector<pair<int,int>>,
greater<pair<int,int>> > pq;
pq.push({0,st});
while(!pq.empty())
{
auto cur = pq.top();
pq.pop();
if(dist[cur.Y]!=cur.X)
continue;
for(auto nxt: adj[cur.Y])
{
if(dist[nxt.Y] <= dist[cur.Y]+nxt.X)
continue;
dist[nxt.Y] = dist[cur.Y] + nxt.X;
pq.push({dist[nxt.Y],nxt.Y});
}
}
return dist[en];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
for(int i=1; i<=m; i++)
{
cin >> a >> b >> cost;
adj[a].push_back({cost,b});
}
for(int i=1; i<=k; i++)
cin >> place[i];
int longest = 0;
int tmp;
for(int i=1; i<=n; i++)
{
int distance = INF;
for(int j=1; j<=k; j++)
{
distance = min(distance, dijkstra(i,place[j]));
}
if(longest < distance)
{
longest = distance;
tmp = i;
}
}
cout << tmp << '\n';
cout << longest;
}위 코드는 시간초과가 났던 코드이다. 무시해도 좋다.
정답 코드
#include <bits/stdc++.h>
#define X first
#define Y second
/*면접장에서 도시까지의 최단경로로 역발상 하는 문재
도시의 수가 10^5, 도로의 길이가 10^5이기 때문에
int 범위를 넘을 가능성이 있어 거리 계산 시에 long long 타입을 사용*/
using namespace std;
typedef long long ll;
vector <pair<ll,int>> adj[100002];
priority_queue <pair<ll,int>, vector<pair<ll,int>>,
greater<pair<ll,int>> > pq;
const ll INF =1e18;
ll dist[100002];
int n,m,k;
int a,b,cost;
void dijkstra()
{
while(!pq.empty())
{
auto cur = pq.top();
pq.pop();
if(dist[cur.Y] != cur.X)
continue;
for(auto nxt : adj[cur.Y])
{
if(dist[nxt.Y] <= dist[cur.Y] + nxt.X)
continue;
dist[nxt.Y] = dist[cur.Y] + nxt.X;
pq.push({dist[nxt.Y],nxt.Y});
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
//면접장으로 부터의 거리를 구하기 위해
for(int i=0; i<m; i++)
{
cin >> a >> b >> cost;
adj[b].push_back({cost,a});
}
fill(dist,dist+n+1,INF);
//면접장이 위치한 정점을 입력받고 거리를 0으로 설정하고 우선순위 큐에 넣는다.
int meet;
for(int i=1; i<=k; i++)
{
cin >> meet;
dist[meet] = 0;
pq.push({0,meet});
}
dijkstra();
//가장 거리가 먼 정점의 인덱스를 찾는다
int idx = max_element(dist+1,dist+n+1) - dist;
ll value = dist[idx];
cout << idx <<'\n' << value;
}
입력받은 도시를 역방향으로 넣어준 것을 볼 수 있다. 또한 면접장이 위치한 도시들의 거리를 모두 0으로 설정하고 우선순위 큐에 넣었다.
