다익스트라 알고리즘 사용 풀이
최단 경로가 여러 개가 나오는 경우 g,h를 지나는 최단경로가 존재하더라도 dijkstra에서 그걸 놓칠 수 있다
input
1
5 5 2
1 2 3
1 4 3
4 5 3
1 2 2
2 3 2
3 5 2
3
5
output: 3
answer: 3 5
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_COST = 987654321;
const int MAX_V = 2000;
int V;
//<u, <v, w>>
vector <pair<int, int>> adj[MAX_V];
//시작 지점에서 각 지점까지의 최소 비용
vector<int> dist(MAX_V, MAX_COST);
//냄새를 맡은 도로(도로의 시작과 끝 정점 저장)
pair<int, int> smellRoad;
//목적지 후보
vector<int> cand;
void priority_queue_dijkstra(int start) {
priority_queue<pair<int, int>> pq;
pq.push(make_pair(0, start));
dist[start] = 0;
//최단 경로 저장
//curNode까지 가는 최단 경로는 curNode 직전에 prevNode를 방문한다
//route[curNode] = prevNode
vector<int> route(V,-1);
while (!pq.empty()) {
int curNode = pq.top().second;
int curW = -pq.top().first;
pq.pop();
for (int i = 0; i < adj[curNode].size(); i++) {
int nextNode = adj[curNode][i].first;
int& nextW = adj[curNode][i].second;
if (dist[nextNode] > curW + nextW) {
dist[nextNode] = curW + nextW;
route[nextNode] = curNode;
pq.push({ -dist[nextNode], nextNode });
}
}
}
//목적지 후보 중 불가능한 경우를 제외한 목록
vector<int> possibleCand;
//start -> dest까지 가는 최단 경로
for (int i = 0; i < cand.size(); ++i) {
int dest = cand[i];
//if (start == dest) continue; 목적지 출발지와 같은 경우 없음
int curNode = dest;
vector<int> destRoute;
destRoute.push_back(curNode);
while (curNode != start) {
curNode = route[curNode];
destRoute.push_back(curNode);
}
reverse(destRoute.begin(), destRoute.end());
//경로에 냄새 맡은 도로가 있는 경우 가능한 목적지
bool possible = false;
for (int j = 0; j < destRoute.size() - 1; ++j) {
int u = destRoute[j];
int v = destRoute[j + 1];
if ((u == smellRoad.first && v == smellRoad.second) || (v == smellRoad.first && u == smellRoad.second)) {
possible = true;
break;
}
}
if (possible) possibleCand.push_back(dest);
}
sort(possibleCand.begin(), possibleCand.end());
for (int i = 0; i < possibleCand.size(); ++i) {
cout << possibleCand[i]+1 << " ";
}
cout << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
//초기화
for (int i = 0; i < MAX_V; ++i) {
adj[i].clear();
dist[i] = MAX_COST;
}
cand.clear();
int n, m; //정점 개수, 도로 개수
int t; //목적지 후보 개수
cin >> n >> m >> t;
V = n;
int s; //출발지
int g, h; //냄새맡은 도로
cin >> s >> g >> h;
s--; g--; h--;
smellRoad = { g, h };
//간선 입력받기
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
u--;
v--;
//양방향 도로
//두 정점 사이 도로 최대 한 개
adj[u].push_back({ v, w });
adj[v].push_back({ u, w });
}
for (int i = 0; i < t; ++i) {
int x;
cin >> x;
x--;
cand.push_back(x);
}
priority_queue_dijkstra(s);
}
return 0;
}
플로이드-와샬 알고리즘 사용 풀이
시간 초과
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_COST = 987654321;
const int MAX_V = 2000;
int V;
//adj[u][v]: u -> v로 가는 최소 비용
//u와 v사이 도로 없는 경우 비용 MAX_COST
int adj[MAX_V][MAX_V];
//플로이드-와샬 알고리즘
void floyd() {
for (int i = 0; i < V; ++i) {
adj[i][i] = 0;
}
//i지점 -> j지점으로 이동할 때 거쳐가는 지점 k
for (int k = 0; k < V; ++k) {
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
//그래프 초기화
for (int i = 0; i < MAX_V; ++i) {
for (int j = 0; j < MAX_V; ++j) {
adj[i][j] = MAX_COST;
}
}
cin >> V; //정점 개수
int m, t; //도로 개수, 목적지 후보 개수
cin >> m >> t;
int s; //출발지점
cin >> s;
s--;
int g, h; //냄새맡은 도로
cin >> g >> h;
g--; h--;
//간선 입력받기
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
u--;
v--;
//양방향 도로
//두 정점 사이 도로 최대 한 개
adj[u][v] = w;
adj[v][u] = w;
}
floyd();
//출발지에서 목적지 후보까지
//g <-> h 도로를 통해서 최단 경로로 갈 수 있는지 확인
vector<int> answer; //가능한 후보
for (int i = 0; i < t; ++i) {
int x; //목적지 후보
cin >> x;
x--;
if (adj[s][x] == (adj[s][g] + adj[g][h] + adj[h][x]))
answer.push_back(x);
else if(adj[s][x] == (adj[s][h] + adj[h][g] + adj[g][x]))
answer.push_back(x);
}
sort(answer.begin(), answer.end());
for (int i = 0; i < answer.size(); ++i) {
cout << answer[i]+1 << " ";
}
cout << "\n";
}
return 0;
}
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_COST = 987654321;
const int MAX_V = 2000;
int V;
//<u, <v, w>>
vector <pair<int, int>> adj[MAX_V];
int s, g, h;
//s에서 각 지점까지의 최소 비용
vector<int> distS(MAX_V, MAX_COST);
//g에서 각 지점까지의 최소 비용
vector<int> distG(MAX_V, MAX_COST);
//h에서 각 지점까지의 최소 비용
vector<int> distH(MAX_V, MAX_COST);
void priority_queue_dijkstra_s() {
priority_queue<pair<int, int>> pq;
pq.push(make_pair(0, s));
distS[s] = 0;
while (!pq.empty()) {
int curNode = pq.top().second;
int curW = -pq.top().first;
pq.pop();
for (int i = 0; i < adj[curNode].size(); i++) {
int nextNode = adj[curNode][i].first;
int& nextW = adj[curNode][i].second;
if (distS[nextNode] > curW + nextW) {
distS[nextNode] = curW + nextW;
pq.push({ -distS[nextNode], nextNode });
}
}
}
}
void priority_queue_dijkstra_g() {
priority_queue<pair<int, int>> pq;
pq.push(make_pair(0, g));
distG[g] = 0;
while (!pq.empty()) {
int curNode = pq.top().second;
int curW = -pq.top().first;
pq.pop();
for (int i = 0; i < adj[curNode].size(); i++) {
int nextNode = adj[curNode][i].first;
int& nextW = adj[curNode][i].second;
if (distG[nextNode] > curW + nextW) {
distG[nextNode] = curW + nextW;
pq.push({ -distG[nextNode], nextNode });
}
}
}
}
void priority_queue_dijkstra_h() {
priority_queue<pair<int, int>> pq;
pq.push(make_pair(0, h));
distH[h] = 0;
while (!pq.empty()) {
int curNode = pq.top().second;
int curW = -pq.top().first;
pq.pop();
for (int i = 0; i < adj[curNode].size(); i++) {
int nextNode = adj[curNode][i].first;
int& nextW = adj[curNode][i].second;
if (distH[nextNode] > curW + nextW) {
distH[nextNode] = curW + nextW;
pq.push({ -distH[nextNode], nextNode });
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
//초기화
for (int i = 0; i < MAX_V; ++i) {
adj[i].clear();
distS[i] = MAX_COST;
distG[i] = MAX_COST;
distH[i] = MAX_COST;
}
int n, m; //정점 개수, 도로 개수
int t; //목적지 후보 개수
cin >> n >> m >> t;
V = n;
cin >> s >> g >> h;
s--; g--; h--;
//간선 입력받기
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
u--;
v--;
//양방향 도로
//두 정점 사이 도로 최대 한 개
adj[u].push_back({ v, w });
adj[v].push_back({ u, w });
}
priority_queue_dijkstra_s();
priority_queue_dijkstra_g();
priority_queue_dijkstra_h();
//목적지 후보 중 불가능한 경우를 제외한 목록
vector<int> answer;
for (int i = 0; i < t; ++i) {
int x;
cin >> x;
x--;
bool possible = false;
if ((distS[x] == (distS[g] + distG[h] + distH[x]))
||(distS[x] == (distS[h] + distH[g] + distG[x]))) possible = true;
if (possible) answer.push_back(x);
}
sort(answer.begin(), answer.end());
for (int i = 0; i < answer.size(); ++i) {
cout << answer[i] + 1 << " ";
}
cout << "\n";
}
return 0;
}
⭐다익스트라 알고리즘에서 최단 경로 출력하기
int V;
//<u, <v, w>>
vector <pair<int, int>> adj[MAX_V];
//시작 지점에서 각 지점까지의 최소 비용
vector<int> dist(MAX_V, MAX_COST);
void priority_queue_dijkstra(int start) {
priority_queue<pair<int, int>> pq;
pq.push(make_pair(0, start));
dist[start] = 0;
//최단 경로 저장
//curNode까지 가는 최단 경로는 curNode 직전에 prevNode를 방문한다
//route[curNode] = prevNode
vector<int> route(V, -1);
while (!pq.empty()) {
int curNode = pq.top().second;
int curW = -pq.top().first;
pq.pop();
for (int i = 0; i < adj[curNode].size(); i++) {
int nextNode = adj[curNode][i].first;
int& nextW = adj[curNode][i].second;
if (dist[nextNode] > curW + nextW) {
dist[nextNode] = curW + nextW;
route[nextNode] = curNode;
pq.push({ -dist[nextNode], nextNode });
}
}
}
//start -> dest까지 가는 최단 경로 출력
for (int dest = 0; dest < V; ++dest) {
if (start == dest) continue;
int curNode = dest;
vector<int> destRoute;
destRoute.push_back(curNode);
while (curNode != start) {
curNode = route[curNode];
destRoute.push_back(curNode);
}
reverse(destRoute.begin(), destRoute.end());
for (int i = 0; i < destRoute.size(); ++i) {
cout << destRoute[i] << " ";
}
cout << "\n";
}
}