https://www.acmicpc.net/problem/12834
팀원이 N명이 주어졌을 때 한 사람의 거리 d = (팀원의 집 ~ KIST의 최단거리) + (팀원의 집 ~ 씨알푸드의 최단거리)로 정의된다.
이때 KIST 또는 씨알푸드까지 도달하지 못한다면 최단거리는 -1로 정의된다.
(둘 다 도달하지 못하는 경우는 d = -2)
최종적으로 Σd 를 구하는 문제이다.
우선 어떤 정점에서 목적지까지의 최단거리를 알아야하므로 다익스트라 알고리즘을 떠올렸다.
팀원의 수 N만큼 각각 다익스트라를 2번 (KIST, 씨알까지의 최단거리) 를 전부 더해주어 해결했다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cmath>
using namespace std;
typedef pair<int, int> pi;
#define endl '\n'
#define MAX 1e9
int n, v, e;
int k, s;
vector<int>home, dist;
vector<vector<pi>>adj;
int dijk(int st, int ed) {
vector<int>dist(v+1, MAX);
priority_queue<pi>pq;
pq.push({0, st});
dist[st] = 0;
while(!pq.empty()) {
int now = pq.top().second;
int cost = -pq.top().first;
pq.pop();
if(dist[now] < cost)continue;
for(auto&node : adj[now]) {
int next = node.second;
int nc = dist[now] + node.first;
if(nc >= dist[next]) continue;
dist[next] = nc;
pq.push({-nc, next});
}
}
return dist[ed];
}
int getResult(int st) {
int homeToKist = dijk(st, k);
int homeToFood = dijk(st, s);
homeToKist = homeToKist == MAX ? -1 : homeToKist;
homeToFood = homeToFood == MAX ? -1 : homeToFood;
return homeToKist + homeToFood;
}
int main(){
scanf("%d %d %d", &n, &v, &e);
scanf("%d %d", &k, &s);
for(int i=0;i<n;++i){
int loc;
scanf("%d", &loc);
home.push_back(loc);
}
adj.resize(v+1);
for(int i=0;i<e;++i){
int a, b, l;
scanf("%d %d %d", &a, &b, &l);
adj[a].push_back({l, b});
adj[b].push_back({l, a});
}
int sum = 0;
for(auto& x : home) {
sum += getResult(x);
}
printf("%d\n", sum);
return 0;
}
팀원을 시작점으로 생각해 다익스트라를 2*N 만큼 돌렸지만 생각해보니 KIST와 씨알푸드의 위치를 시작점으로 생각하고 팀원의 위치를 목적지로 생각한다면 다익스트라를 두 번만 돌려도 될 것이다.
다익스트라를 돌리는 횟수가 확 줄었기 때문에 시간이 많이 단축되었음을 확인할 수 있다.
시작점, 끝점을 잘 생각해서 적용하고 풀어보자!
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cmath>
using namespace std;
typedef pair<int, int> pi;
#define endl '\n'
#define MAX 1e9
int n, v, e;
int k, s;
vector<int>home, dist;
vector<vector<pi>>adj;
int dijk(int st) {
vector<int>dist(v+1, MAX);
priority_queue<pi>pq;
pq.push({0, st});
dist[st] = 0;
while(!pq.empty()) {
int now = pq.top().second;
int cost = -pq.top().first;
pq.pop();
if(dist[now] < cost)continue;
for(auto&node : adj[now]) {
int next = node.second;
int nc = dist[now] + node.first;
if(nc >= dist[next]) continue;
dist[next] = nc;
pq.push({-nc, next});
}
}
int sum = 0;
for(auto& x : home) {
sum += (dist[x]==MAX) ? -1 : dist[x];
}
return sum;
}
int main(){
scanf("%d %d %d", &n, &v, &e);
scanf("%d %d", &k, &s);
for(int i=0;i<n;++i){
int loc;
scanf("%d", &loc);
home.push_back(loc);
}
adj.resize(v+1);
for(int i=0;i<e;++i){
int a, b, l;
scanf("%d %d %d", &a, &b, &l);
adj[a].push_back({l, b});
adj[b].push_back({l, a});
}
printf("%d\n", dijk(k) + dijk(s));
return 0;
}