문제 링크
http://acm.kaist.ac.kr/2008/ProblemSet.pdf , C - Homing
문제 설명
어떤 사람이 출발지에서부터 목적지까지 자동차를 운전해서 가려고 합니다. 출발지와 목적지 사이에는 여러 도시들이 있고 서로 연결된 도시간의 거리 정보( = 그 길을 가는 데에 쓰이는 연료량)가 주어집니다. 이 사람은 출발지에서부터 목적지까지 가는 데에 필요한 최소한의 연료만을 넣어서 출발하고 싶습니다. 그러나 한 가지 문제가 있는데, 이 사람이 목적지를 향하던 도중에 기존에 존재하던 연결 중 최대 한 쌍 도시의 연결이 끊어질 수 있습니다. 그런데 이 사람은 그 연결이 끊어졌다는 것을 연결이 끊어진 끊어진 도시에 도착하였을 때 알 수 있습니다. 위와 같은 사실을 명심하며, 이 사람이 최소한 얼마나 많은 연료를 출발점에서 넣어야만 도착점에 무사히 도착할 수 있을까요? 도시의 숫자와 도시간 연결의 숫자는 모두 1이상 만 이하입니다. 모든 연결쌍이 무사할 경우의 최단거리 경로 역시 입력으로 주어집니다.
문제 풀이
[spoiler="더 보기..."]최대 한 쌍의 도로에 사고가 생길 수 있다는 사실에 주목해 보겠습니다.
i) 만약 사고가 생긴 도로가 최단경로상에 있는 도로가 아니라면?
이 때 여행자는 최단경로에서 필요한 연료만을 준비해서 가면 됩니다.
ii) 만약 사고가 생긴 도로가 최단경로상에 있는 도로 중 하나라면?
최단경로가 도시 s a b c d e t 를 순서대로 여행하는 것이라 가정하겠습니다. 만약에 b와 c를 연결하는 도로에 사고가 생겼다면, 여행자는 도시 b에 도착하였을 당시에 그 사실을 알 수 있습니다. 그럼 이 사실을 알아차린 시점에서 여행자가 도착지까지 가장 빠르게 갈 수 있는 방법은 b-c를 거치지 않으면서, b에서 가능한 가장 빠르게 t로 갈 수 있는 경로를 찾아보는 것입니다. 즉 이 문제는 b-c 의 거리가 무한대일 때 b에서 t까지의 최단경로를 찾는 것과 같습니다. 그 후에 s부터 b까지 가는 길에 걸리는 연료량을 더해준다면 b-c 도로에 사고가 생겼을 시 전체 여행에 필요한 최소의 연료량을 구할 수 있습니다. 위와 같은 방법을 s-a 도로에 사고가 생겼을 때, a-b 도로에 사고가 생겼을 때, ... e-t 도로에 사고가 생겼을 때를 각각 가정하여 최단거리를 계산해 보고, 그 최단거리중 가장 큰 값을 여행자가 필요한 최소의 연료량으로 생각하면 문제는 해결됩니다.
사고가 생긴 도로의 인접도시에 도착하였을 때, 현재 도시에서 도착지까지의 최단 거리는 다익스트라를 통해서 구할 수 있습니다( O(VlgE) ). 이 다익스트라를 최단경로상에 있는 모든 도로의 갯수번 수행해야 함으로 다익스트라를 최대 (V-1)번 수행해야 합니다. 고로 본 풀이의 시간복잡도는 O(V^{2lgE)입니다.}
사실 저는 대회 당시에 이 문제를 해결하지 못하였기 때문에 본 풀이가 실제 데이터에서 올바르게 작동할지 확신하지는 못합니다. 다만 YES를 받았던 팀 선수의 말에 따르면 이 풀이와 같은 시간복잡도로 실제 대회에서는 통과되었다고 합니다. 이 풀이 외에도 다른 풀이가 있다면 들어보고싶네요~[/spoiler]
코드
~~~ cpp

#include
#include
#include
using namespace std;
template
class Dijkstra
{
public:
enum { INF = 1000000002 };
vector > > eList;
vector isVisit;
Dijkstra(int n) { eList.resize(n); }
void addEdge(T cost, int from, int to)
{
eList[from].push_back(make_pair(cost, to));
return;
}
T editCost(T cost, int from, int to)
{
T ret=-1;
int i;
for(i=0;i {
if(eList[from][i].second==to) { ret=eList[from][i].first; break; }
}
eList[from][i].first=cost;
return ret;
}
void getDist(int start, vector &dist)
{
dist.clear();
dist.resize(eList.size());
isVisit.clear();
isVisit.resize(eList.size());
for(int i=0;i priority_queue , vector >, greater > > Q;
Q.push(make_pair(0, start));
for(int i=0;i {
while(!Q.empty() && isVisit[Q.top().second]) Q.pop();
if(Q.empty()) break;
pair cur=Q.top();
isVisit[cur.second]=true;
dist[cur.second]=cur.first;
int now=cur.second;
T d=dist[cur.second];
for(int j=0;j if(!isVisit[eList[now][j].second])
Q.push(make_pair(d+eList[now][j].first, eList[now][j].second));
Q.pop();
}
return;
}
};
int main(void)
{
int t;
scanf("%d", &t);
while(t--)
{
int n, m;
scanf("%d %d", &n, &m);
Dijkstra *graph = new Dijkstra (n);
for(int i=0;i {
int temp[3];
scanf("%d %d %d", temp, temp+1, temp+2);
graph->addEdge(temp[2], temp[0], temp[1]);
graph->addEdge(temp[2], temp[1], temp[0]);
}
int k, ans=-1;
vector dist, route;
scanf("%d", &k);
for(int i=0;i for(int i=1;i {
int bef=graph->editCost(1000000002, route[i-1], route[i]);
graph->editCost(1000000002, route[i], route[i-1]);
graph->getDist(route[0], dist);
int temp=dist[route[i-1]];
graph->getDist(route[i-1], dist);
temp+=dist[route[route.size()-1]];
ans=max(ans, temp);
graph->editCost(bef, route[i-1], route[i]);
graph->editCost(bef, route[i], route[i-1]);
}
if(ans>=1000000002) printf("-1n");
else printf("%dn", ans);
delete graph;
}
return 0;
}

<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/54852">원문보기</a>]</div>