https://www.acmicpc.net/problem/1753
문제
> 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오.
> 단, 모든 간선의 가중치는 10 이하의 자연수이다.
> 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다.
(1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000)
> 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다.
> 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다.
> 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다.
> 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다.
> u와 v는 서로 다르며 w는 10 이하의 자연수이다.
> 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.접근
입력으로 들어오는 정점들의 관계를 통해 관계도를 방향을 생각해서 만들어주고 Graph 메소드에서 우선순위 큐를 만들어 시작 가중치(0)과, 시작 정점을 넣고 시작한다.
그럼 시작정점에서 갈 수 있는 정점들이 다음 큐에 들어오는데 우선순위 큐이므로 가중치가 낮은 순서대로 정렬된다.
큐에서 또 다음 top을 뽑아오고 여기서 갈 수 있는 정점까지의 가중치, 정점 번호가 큐에 오름차순으로 들어간다.
이 과정을 반복하며 방문처리를 하면 최단거리로만 뽑혀지게 된다. 그러면 결과를 저장할 rst벡터에 각 정점을 인덱스로 해서 해당 인덱스까지 누적된 가중치를 값으로 가져 거리를 나타낸다. 만약 갈 수 없다면 rst벡터의 초기값을 INF로 줬기 떄문에 INF로 나온다.
문제해결
> 정점의 관계를 저장할 num벡터에 u점을 인덱스로 하고 w, v순으로 쌍으로 입력받아 저장한다.
> Graph 메소드에 시작가중치 0, 시작정점 K를 넣고 호출한다.
> Graph 메소드에서는 우선순위 큐를 쌍으로 입력받고, 오름차순 정렬하게 선언해주며 인자로 들어온 p를 큐의 시작값을 넣고 시작한다.
> 시작 정점 K부터 가능한 모든 정점을 돌며 rst에 fnode로 뽑아온 정점에 대해 weight값을 저장해 해당 정점까지의 거리를 저장한다.
> 우선순위 큐에서 최소값이 뽑혀오고, 방문처리로 다시는 뽑히지 않기 때문에 최소값만 저장이 되는 원리로 이를 처리한다.
> for문을 통해 fnode에서 갈 수 있는 정점을 큐에 넣어주는데 이때, 해당 정점에서 그 정점까지의 거리를 누적해야하므로 현재의 weight + 해당 정점까지의 가중치를 더한 값을 넘긴다.
> main에서 rst(1)~ rst(V)까지 출력하는데 rst는 문자열형 벡터고 초기값은 INF이다. Graph메소드 안에서 나온 정점간 거리를 to_string으로 변환해서 넣었기 때문에 만약 특정 정점까지 못간다면 INF가 나오고 갈 수 있다면 저장된 거리가 나온다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int V, E, K;
vector<vector<pair<int, int>>> num;
vector<bool> visited;
vector<string> rst;
void Graph(pair<int, int> p)
{
rst.resize(V + 1, "INF");
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push(p);
while (!pq.empty())
{
int weight = pq.top().first;
int fnode = pq.top().second;
pq.pop();
if (visited[fnode]) continue;
visited[fnode] = true;
rst[fnode] = to_string(weight);
for (auto a : num[fnode])
{
pq.push({ a.first + weight, a.second });
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> V >> E;
cin >> K;
num.resize(V + 1, vector<pair<int, int>>());
while (E--)
{
int a, b, c;
cin >> a >> b >> c;
num[a].push_back({ c, b });
}
visited.assign(V + 1, false);
Graph({ 0, K });
for (int i = 1; i <= V; i++)
{
cout << rst[i] << '\n';
}
}
후기
정점 V에 대해서 Graph메소드를 반복문으로 V번 반복해서 값을 반환하고 이를 출력했더니 시간초과가 났다.
그래서 시작점은 정해줬기 때문에 Graph 메소드에서 시작점부터 갈 수 있는 곳을 탐색하면 while문에서 알아서 각 정점 까지 방문처리로 인해 거리가 저장되기 때문에 해당 정점을 큐에서 뽑을 때 그 정점의 쌍으로 들어온 가중치를 저장하게 했다. 그럼 INF는 가본적이 없어 처리 못하기 때문에 rst를 문자열형으로 초기값 INF로 주고 안갔으면 초기값이 나오도록 헀더니 맞았다.
