[문제 링크]
각 도시에서 한 도시로의 왕복 최단 거리 중에 최장 거리를 구하는 문제이다(?)
directed graph이기 때문에 X라는 도시에 갈 때와, X라는 도시에서 돌아 올 때의 경로는 둘 다 다르다.
난 이 문제를 3가지 방법으로 풀었다.
.
1. 플로이드-와샬 알고리즘으로 전체 최단 경로를 구해 푸는 방법.
플로이드-와샬 알고리즘으로는 코드도 정말 간단하고,정답도 잘 나왔지만, 플로이드-와샬 자체가 O(n^3)인 알고리즘인지라 시간초과가 났다. 가지치기를 잘 하면 accept 되는거 같긴 한데, 그래도 다익스트라를 이용하는 것 보다는 느릴거란 생각이 들었다.(또 아무래도 정점의 갯수에 비헤 간선이 워낙 적기 때문이기도 한거같다.)
2. 다익스트라 알고리즘으로 X에서 출발하는 모든 최단 경로를 구한 뒤, 각 정점별로의 최단거리 또한 구해서 X까지 가는 방법.
모든 정점에 대해서 다익스트라 알고리즘을 사용해서 최대값을 구했다. 이건 accept가 뜨긴 떴다. 하지만 개인적으로 만족스럽지 않았다. 실행 속도도 속도지만, 굳이 각 정점에 대해서 최단 거리를 구할 필요가 있나 생각이 들었다.
3. 다익스트라 알고리즘으로 X에서 출발하는 모든 최단 경로를 구한 뒤, 모든 간선을 뒤집어서 X에서 출발하는 정점을 구하는 방법.
일단 정방향으로 되어있는 인접리스트로 최단 경로를 구하고, 그다음 역방향으로 되어있는 인접리스트로 최단 경로를 구했다.
그냥 간선만 방향을 바꿔주면 다른 모든 정점에서 X로 오는 정점을 구하는 것과 다를 게 없다. 따라서 2번과는 다르게 다익스트라 알고리즘을 단 2번만 사용해서 최대값을 구할 수 있다.
1. 플로이드-와샬 알고리즘으로 구현한 코드
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#define MAX 987654321
using namespace std;
int n, m, x;
vector<vector<int> > fw;
int main() {
scanf("%d %d %d", &n, &m, &x);
fw.resize(n + 1);
for (int i = 0; i<n; i++) {
for (int j = 0; j<n; j++) {
fw[i].push_back(MAX);
if (i == j) fw[i][j] = 0;
}
}
for (int i = 0; i<m; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
fw[u - 1][v - 1] = w;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j<n; j++) {
for (int k = 0; k<n; k++) {
if (fw[k][j] > fw[k][i] + fw[i][j])
fw[k][j] = fw[k][i] + fw[i][j];
}
}
}
int ret = 0;
for (int i = 0; i<n; i++)
ret = max(ret, fw[i][x] + fw[x][i]);
printf("%d", ret);
}
2. 다익스트라 알고리즘 N번으로 구현한 코드
#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
#define MAX 987654321
using namespace std;
vector<vector<pair<int, int> > > adj;
int n, m, x;
typedef pair<int, int> node;
struct cmp {
bool operator()(node x, node y) {
return x.second > y.second;
}
};
int ret[1001] = {0,};
void dijkstra(int x,int y) {
priority_queue<node, vector<node>, cmp> pq;
vector<int> dist(n+1,MAX); dist[x] = 0;
pq.push(make_pair(x,0));
for(int i=0; i<n;i++){
if(i!=x) pq.push(make_pair(i,MAX));
}
while(!pq.empty()){
int u = pq.top().first;
int d = pq.top().second; pq.pop();
if(d > dist[u]) continue;
for(int i = 0; i<adj[u].size(); i++){
int v = adj[u][i].first;
int w = adj[u][i].second;
if(dist[v] > dist[u] + w){
dist[v] = dist[u] + w;
pq.push(make_pair(v,dist[v]));
}
}
}
if(y==x){
for(int i = 0; i<n; i++) ret[i] = dist[i];
}
else{
ret[x] += dist[y];
}
}
int main() {
scanf("%d %d %d", &n, &m, &x);
adj.resize(n + 1);
for (int i = 0; i<m; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
adj[u-1].push_back(make_pair(v-1, w));
}
dijkstra(x-1,x-1);
for(int i=0; i<n; i++){
if(i!=x)
dijkstra(i,x);
}
int mv = 0;
for(int i=0; i<n;i++) mv = max(mv,ret[i]);
printf("%d",mv);
}
3. 다익스트라 알고리즘 2번으로 구현한 코드
#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
#define MAX 987654321
using namespace std;
vector<vector<pair<int, int> > > adj1, adj2;
int n, m, x;
typedef pair<int, int> node;
struct cmp {
bool operator()(node x, node y) {
return x.second > y.second;
}
};
int ret[1001] = {0,};
void dijkstra(int x, vector<vector<pair<int,int> > > adj) {
priority_queue<node, vector<node>, cmp> pq;
vector<int> dist(n+1,MAX); dist[x] = 0;
pq.push(make_pair(x,0));
for(int i=0; i<n;i++){
if(i!=x) pq.push(make_pair(i,MAX));
}
while(!pq.empty()){
int u = pq.top().first;
int d = pq.top().second; pq.pop();
if(d > dist[u]) continue;
for(int i = 0; i<adj[u].size(); i++){
int v = adj[u][i].first;
int w = adj[u][i].second;
if(dist[v] > dist[u] + w){
dist[v] = dist[u] + w;
pq.push(make_pair(v,dist[v]));
}
}
}
for(int i = 0; i<n; i++) ret[i] += dist[i];
}
int main() {
scanf("%d %d %d", &n, &m, &x);
adj1.resize(n + 1);
adj2.resize(n + 1);
for (int i = 0; i<m; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
adj1[u-1].push_back(make_pair(v-1, w));
adj2[v-1].push_back(make_pair(u-1, w));
}
dijkstra(x-1,adj1);
dijkstra(x-1,adj2);
int mv = 0;
for(int i=0; i<n;i++) mv = max(mv,ret[i]);
printf("%d",mv);
}