submit 하는걸 목표로 했었는데, 감기 몸살로 쓰러지는 바람에 목표 달성에 실패한 Toivoa 입니다.
문제나 읽어보려고 보다가 D 문제가 난이도에 비해 맞은 사람이 적길래 뭐가 문제였을지 생각해보다가 에디토리얼을 쓰게 되었습니다.
[spoiler="문제 풀이"][문제 풀이]
이 문제는 어린이의 현재 위치 -> 오페라 하우스 -> 호텔로 가는 경로를 구하겠다고 들면 풀기 어렵습니다.
문제를 살짝 바꿔서 생각해보면 오페라 하우스 -> 현재 위치와 오페라 하우스 -> 호텔로 가는 서로 겹치지 않는 두 경로를 찾는 것과 같다는 것을 알 수 있습니다. (방향 그래프라면 이러면 안되겠지요)
이렇게 하면 생각나는 것이 flow가 2인 min-cost max-flow를 하면 되겠다! 입니다. 하지만 min-cost max-flow는 코딩하기도 귀찮고, 익숙하지 않고.... 의 문제가 있는데, flow가 항상 2인 특성을 이용해서 요즘 KOI에 나오는 초등학생들도 다 안다는 국민 알고리즘인 Dijkstra와 Floyd의 shortest path algorithm의 조합으로 충분히 풀 수 있습니다. max-flow를 제대로 이해하고 있다면 이렇게 풀 수 있다는 것을 쉽게 이해할 수 있습니다.
문제 풀이 단계는 다음과 같습니다.
1. Dijkstra algorithm을 이용해서 오페라 하우스 -> 현재 위치로의 경로를 찾고, 최단 거리를 r1이라고 합시다.
2. 두 번째 경로를 찾는 과정에서 1번에서 찾은 경로를 cancel할 수 있도록 정방향 경로는 없애고, 역방향은 음수 거리로 변경합니다. (이 부분이 이해되지 않는다면 max-flow. 특히 Ford-Fulkerson algorithm을 공부해보세요.)
3. 또 Dijkstra algorithm을 이용하려 하니 음수 cost를 가진 edge가 있기 때문에 사용할 수 없습니다. 이번에는 Floyd algorithm을 이용해서 오페라 하우스 -> 호텔로의 최단 거리를 구해서 이를 r2라고 합시다.
4. 답은 r1 + r2가 됩니다.
[사족]
이렇게 풀어서 공개된 데이터와 비교해봤더니 틀리길래 뭐가 문제인가? 하고 보니 대회 은퇴한지 오래되다 보니 UVA 100번 문제의 교훈인 "문제에 나와 있지 않은 어떤 것도 가정하지 말라"는 것을 잊어서 생긴 문제였습니다.
이 문제의 입력에는 입력으로 같은 vertex 쌍을 잇는 edge가 여러개 들어올 수 있습니다.
잠시 생각해보면 같은 vertex 쌍이 여러개 들어오면 문제의 특성상 cost가 가장 작은 두개만 필요하고, Dijkstra, Floyd algorithm을 이용할 때에는 그 중에 (현재 가장 작은) edge만을 사용하면 됩니다. 아래 첨부된 소스코드는 이 성질을 이용하고 있습니다.
유사 문제로는 uva에 Dijkstra, dijkstra 문제가 있습니다. (http://acm.uva.es/p/v108/10806.html)
[/spoiler]
 
[spoiler="소스 코드 보기"]~~~ cpp

#include
#include
#include
#include
using namespace std;
#define MAX_DIST 1000000
int table[100][100][2];
vector v[100];
int t, n, m;
struct in_que
{
        int now;
        int dist;
        bool operator < (const in_que& rhs) const
        {
                return dist > rhs.dist;
        }
};
int dijkstra(int s, int e)
{
        int dist[100], from[100];
        in_que c, d;
        priority_queue q;
        c.now = s; c.dist = 0;
        q.push(c);
        fill(dist, dist + 100, MAX_DIST);
        from[s] = -1; dist[s] = 0;
        while (!q.empty())
        {
                c = q.top(); q.pop();
                if (c.now == e)
                {
                        int x = e, y = from[e];
                        while (y != -1)
                        {
                                table[x][y][0] = -table[x][y][0];
                                table[y][x][0] = table[y][x][1];
                                x = y; y = from[y];
                        }
                        return c.dist;
                }
                for (size_t i = 0; i < v[c.now].size(); ++i)
                {
                        d.now = v[c.now][i];
                        d.dist = c.dist + table[c.now][d.now][0];
                        if (dist[d.now] > d.dist)
                        {
                                q.push(d);
                                dist[d.now] = d.dist;
                                from[d.now] = c.now;
                        }
                }
        }
        return MAX_DIST;
}
int floyd(int s, int e)
{
        for (int k = 0; k < n; ++k)
                for (int i = 0; i < n; ++i)
                        for (int j = 0; j < n; ++j)
                                table[i][j][0] <?= table[i][k][0] + table[k][j][0];
        return table[s][e][0];
}
int main()
{
        scanf("%d", &t);
        while (t--)
        {
                scanf("%d%d", &n, &m);
                fill(table[0][0], table[100][0], MAX_DIST);
                for (int i = 0; i < n; ++i)
                        v[i].clear();
                for (int i = 0; i < m; ++i)
                {
                        int x, y, z;
                        scanf("%d%d%d", &x, &y, &z);
                        --x, --y;
                        for (int j = 0; j < 2; ++j)
                                if (table[x][y][j] > z)
                                {
                                        int temp = table[x][y][j];
                                        table[x][y][j] = table[y][x][j] = z;
                                        z = temp;
                                }
                        v[x].push_back(y);
                        v[y].push_back(x);
                }
                printf("%dn", dijkstra(1, 0) + floyd(1, n - 1));
        }
}

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