https://www.acmicpc.net/problem/1238
풀이
다익스트라를 이용하는 문제이다.
1. 선언한 vector에 입력받은 시작위치에 끝점과 소요시간을 저장한다.
2. 시작 idx인 i 부터 X까지의 거리를 구한다.
3. X번 마을에서부터 다시 i 까지 돌아가는 거리를 구한다.
다익스트라 함수는 흔히 알고있는 다익스트라를 구현한다.
해당 거리를 저장하는 배열을 지속적으로 갱신해주고, 결과값에 저장후, 최대값을 찾아 출력해준다.
Code ( C++ )
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
// 학생 수
int N;
// 도로 수
int M;
// 파티하는 마을
int X;
// 이동 최소거리 저장
int _distance[1001];
// 오름차순 정렬 큐
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<pair<int, int>> _vec[1001];
void Dijkstra(int idx)
{
// init
fill(_distance, _distance + 1001, -1);
_distance[idx] = 0;
pq.push({ 0,idx });
while (!pq.empty())
{
int d = pq.top().first;
int x = pq.top().second;
pq.pop();
for (int i = 0; i < _vec[x].size(); i++)
{
int mx = _vec[x][i].first;
int md = _vec[x][i].second;
// 처음 방문하거나, 큐에 있는 짧은 거리가 다음 방문할곳을 더한 거리보다 짧을 경우
if (_distance[mx] == -1 || _distance[mx] > d + md)
{
// 다음 방문 거리까지 더한 후 갱신
_distance[mx] = d + md;
pq.push({ _distance[mx], mx });
}
}
}
}
int main()
{
int result[1001] = { 0, };
int ans = 0;
cin >> N >> M >> X;
while (M--)
{
int s, e, t;
cin >> s >> e >> t;
// 시작위치에 끝점과 소요시간 저장
_vec[s].push_back({ e,t });
}
// 시작 idx에서 X까지의 거리
for (int i = 1; i <= N; i++)
{
// 같은 위치인 경우 제외
if (i == X)
continue;
Dijkstra(i);
result[i] = _distance[X];
}
Dijkstra(X);
// 다시 돌아가는 거리 추가
for (int i = 1; i <= N; i++)
{
result[i] += _distance[i];
}
for (int i = 1; i <= N; i++)
ans = max(ans, result[i]);
cout << ans;
}
'💻 OnlineJudge > Baekjoon' 카테고리의 다른 글
[백준 / BOJ] C++ 1629 곱셈 (0) | 2022.11.10 |
---|---|
[백준 / BOJ] C++ 1504 특정한 최단 경로 (0) | 2022.11.10 |
[백준 / BOJ] C++ 1167 트리의 지름 (0) | 2022.11.03 |
[백준 / BOJ] C++ 1149 RGB거리 (0) | 2022.11.02 |
[백준 / BOJ] C++ 1043 거짓말 (1) | 2022.10.28 |