1. 문제 링크
2. 소스코드
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#define MAX_N 101
#define MAX_V 1001
using namespace std;
int loc[MAX_N];
int dist[MAX_V][MAX_V];
long long int shortest[2][MAX_V];
int n, v, e, goal1, goal2, temp1, temp2, tempv, nextv;
long long int tempd, ans = 0;
int cnt = 0;
priority_queue<pair<long long int, int>, vector<pair<long long int, int>>, greater<pair<long long int, int>>> q;
void dijkstra(int loc, vector < vector<int>> adj) {
shortest[cnt][loc] = 0;
tempv = loc;
tempd = 0;
long long int nextd;
int nextv;
q.push(make_pair(0, loc));
while (!q.empty()) {
tempd = q.top().first;
tempv = q.top().second;
q.pop();
for (auto e : adj[tempv]) {
nextv = e;
nextd = tempd + dist[tempv][nextv];
if (shortest[cnt][nextv] != -1&& nextd >= shortest[cnt][nextv])continue;
else {
shortest[cnt][nextv] = nextd;
q.push(make_pair(nextd, nextv));
}
}
}
return;
}
int main() {
memset(shortest, -1, sizeof(shortest));
cin >> n >> v >> e >> goal1 >> goal2;
vector<vector<int>> adj(v + 1, vector<int>(0,0));
for (int i = 0;i < n;i++) {
cin >> loc[i];
}
for (int i = 0;i < v;i++)dist[i][i] = 0;
for (int i = 0;i < e;i++) {
cin >> temp1 >> temp2 >> tempd;
if (dist[temp1][temp2] != 0 && tempd > dist[temp1][temp2])continue;
dist[temp1][temp2] = dist[temp2][temp1] = tempd;
adj[temp1].push_back(temp2);
adj[temp2].push_back(temp1);
}
dijkstra(goal1, adj);cnt++;
dijkstra(goal2, adj);
for (int i = 0;i < n;i++) {
if (shortest[0][loc[i]] == -1)ans += -1;
else ans += shortest[0][loc[i]];
if (shortest[1][loc[i]] == -1)ans += -1;
else ans += shortest[1][loc[i]];
}
cout << ans;
return 0;
}3. 노트
3-1.Dijkstra를 이용한 최단거리 알고리즘
다익스트라 알고리즘은 하나의 노드에서 다른 모든 노드로 가는 최단거리를 각각 구하는 알고리즘이다. 이번 문제에서처럼 두 가지 목적지에 대한, 다른 모든 노드에서의 최단거리의 합을 구할 때는, 각각의 다익스트라 연산에서 공통되는 노드를 출발 노드로 설정하여 다익스트라 연산을 진행하면 된다. 즉, 목적지를 출발 노드로 설정하여 다른 모든 노드로의 다익스트라 연산을 수행하면 두 번의 연산으로도 답을 구할 수 있다.
3-2.자료구조
-이차원 벡터를 이용한 인접 리스트
다익스트라 알고리즘에서는 아직 방문하지 않은 노드들 중, 현재까지 탐색한 모든 노드 각각의 인접 노드 중 가장 거리가 가까운 노드를 다음으로 탐색한다. 노드 간 인접 관계를 나타나기 위해 인접 리스트를 구현하였다.
-우선순위 큐-다음으로 탐색할 노드를 저장
우선순위 큐에 (출발 노드로부터의 거리, 정점의 인덱스) 쌍을 저장하였다. 이 때 출발 노드로부터의 거리를 기준으로 오름차순으로 정렬하였는데, 정렬을 구현할 때 operator 함수를 오버라이딩하는 방법도 있고,
priority_queue <pair<int,int>, cmp> q;에서의 cmp를 정의하여 구현하는 방법이 있는데, pair를 저장하는 우선순위 큐에서도 greater을 이용하여 오름차순 정렬의 구현이 가능하다.문법은 왜인지 모르겠지만 다음과 같다.
priority_queue<pair<long long int, int>, vector<pair<long long int, int>>, greater<pair<long long int, int>>> q;-이차원 배열을 이용하여 각 노드간의 거리, 노드-노드간의 최단거리 저장
이 때 출발 노드와 아직 탐색하지 않은 노드간의 거리를 무한대(적당히 큰 수)로 초기화하려고 했으나, C++에서 memset함수를 이용하여 int를 저장하는 배열을 초기화할 때에는 배열의 모든 원소를 -1,0,1 중 하나의 값으로만 초기화할 수 있고, 이외의 값으로는 초기화가 불가능하다.
이는 memset(arr, defaultValue, sizeof(arr));로 함수를 실행할 경우, 실제로는 원소가 unsigned char 형태로 저장되어, 1byte 단위로 defaultValue로 초기화되고, 이에 따라 4byte 자료형인 int와의 오차가 발생하는 것이다.
이에 따라 나는 출발 노드와 아직 탐색하지 않은 노드 간의 거리를 -1로 초기화하였고, 다익스트라 연산을 진행했는데도 아직 거리가 -1인 노드를, 그래프상 연결되지 않아 방문할 수 없는 노드로 판단하였다.
3-3.메모
사실 내가 구현한 코드의 초안이, 내가 대입한 모든 input에 대해 정답을 출력하였지만 왜인지 채점을 돌리면 72%에서 틀렸습니다가 나왔다 ㅠㅠ 왜 그랬는지는 더 알아보고 추후에 올리도록 하겠다.
++나는 에디터로 Visual studio를 이용하는데, Visual studio에서는 잘만 돌아가던 코드가 채점 서버에서는 대체 무슨 오류를 발생시키나 싶어 온라인 C++ 컴파일러를 이용하여 코드를 Run해 보았다. 그런데 Visual studio에서는 잘 실행되던 코드가 Segmentation fault을 일으키는 것을 확인하고 이에 따라 작은 오류를 수정할 수 있었다. 진짜 내가 쓰는 에디터에서는 잘만 돌아가는 코드에 무언가 문제가 있다면, 온라인 컴파일러를 이용해 보는 것도 괜찮을 것 같다.
참고로 내가 이용한 사이트는
https://www.onlinegdb.com/online_c++_compiler 이다.
