N개의 정점이 있고 각 정점에서 특정 점정 X가 정해진다. 이때 각 정점에서 i를 방문하고 다시 자기 자신의 정점으로 돌아오는 최소 길이를 구한 뒤 가장 많은 비용을 소비하는 정점을 구하는 문제이다.
첫째 줄에 N(1 <= N <= 1,000), M(1 <= M <= 10,000), X가 공백dmfh rnqnsehldj dlqfurehlsek.
두 번째 줄부터 M + 1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 T가 들어온다.
예시
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3
예제 출력
10
어디서 힌트를 얻을 수 있을까?
위의 문제를 처음 봤을 때 정점과 간선 그리고 최소 비용이라는 키워드를 통해서 그래프 탐색 문제라는 것을 알 수 있었다.
하지만 내가 아는 BFS를 적용하기에는 방문했던 노드를 또 들릴 수도 있다는 가능성 때문에 적용을 할 수가 없었다.
그렇다고 DFS를 적용하기에는 각 정점에서 도착 정점 까지의 거리와 도착 정점에서 각 정점까지의 거리를 일일이 구해야 하는데 이렇게 되면 시간 복잡도가 O(n^3)이 되기 때문에 시간을 초과할 것 같았다.
그렇게 고민을 하던 중 다익스트라라는 알고리즘을 접하게 되었다.
다익스트라 알고리즘은 간단하게 말해서 주어진 정점에서 각 정점 까지의 최단 거리를 구할 수 있는 알고리즘이다.
그러면 기존에 입력 받았던 간선을 두 가지 방법으로 받기로 했다.
위의 두 방법을 구한 뒤 더하고 그 중 최대 비용을 구하면 이 문제를 해결할 수 있다.
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <cstring>
struct Node {
int idx;
int dis;
};
struct cmp {
bool operator()(std::pair<int, int> a, std::pair<int, int> b)
{
if (a.second > b.second)
return true;
else if (a.second == b.second)
{
if (a.first > b.first)
return true;
else
return false;
}
return false;
}
};
int INF = 999999;
std::vector<Node> varr[2][1001];
int disArr[2][1001];
void Dijkstra(int flag, int Node)
{
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, cmp> pqarr;
pqarr.push(std::make_pair(Node, 0));
disArr[flag][Node] = 0;
int tmpNode;
int tmpDis = 0;
while (!pqarr.empty())
{
tmpNode = pqarr.top().first;
tmpDis = pqarr.top().second;
pqarr.pop();
if (tmpDis > disArr[flag][tmpNode])
continue;
for (int i = 0; i < varr[flag][tmpNode].size(); i++)
{
int nextNode = varr[flag][tmpNode][i].idx;
int nextDis = varr[flag][tmpNode][i].dis;
if (disArr[flag][nextNode] > tmpDis + nextDis && nextNode != Node)
{
disArr[flag][nextNode] = tmpDis + nextDis;
pqarr.push(std::make_pair(nextNode, disArr[flag][nextNode]));
}
}
}
}
void init(void)
{
for (int i = 0; i < 1001; i++)
{
disArr[0][i] = INF;
disArr[1][i] = INF;
}
}
int main(void)
{
int N, M, X;
std::cin >> N >> M >> X;
for (int i = 0; i < M; i++)
{
int S, D, T;
std::cin >> S >> D >> T;
varr[0][D].push_back({S, T});
varr[1][S].push_back({D, T});
}
init();
Dijkstra(0, X);
Dijkstra(1, X);
int ret = 0;
for (int i = 1; i <= N; i++)
{
if (i != X)
ret = std::max(ret, disArr[0][i] + disArr[1][i]);
}
std::cout << ret << std::endl;
return 0;
}
https://www.acmicpc.net/problem/1238
1238번: 파티
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어
www.acmicpc.net
다익스트라(Dijkstra) 알고리즘
다익스트라(Dijkstra) 알고리즘은 그래프 이론을 활용한 대표적인 최단 경로(Shortest Path)탐색 알고리즘이다. 이 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수
deulee.tistory.com
백준 12930 - 두 가중치(C++) (0) | 2023.05.23 |
---|---|
백준 1753 - 최단경로(C++) (0) | 2023.05.22 |
백준 1629 - 곱셈(C++) (0) | 2023.05.22 |
백준 1504 - 특정한 최단 경로(C++) (0) | 2023.05.21 |
백준 1167 - 트리의 지름(C++) (1) | 2023.05.20 |