[[problem:MOVE]]문제입니다. 오답의 원인을 못찾은지도 벌써...
[[problem:ROUTING]] 문제와 비슷해 보여 풀만하다고 도전했는데 꽉 막혔네요;;

알고리즘은 딕스트라+priority_queue를 썼습니다. 혹시 아래 말고 문제풀이 시 주의해야할 점이 있을까요?
1. 두 도시 간에 복수의 도로 존재 가능. -> 입력 시, 더 짧은 길이로 덮어씀
2. 도로는 양 방향 -> 도로 경로 입력 시, 대칭되게 neighbor vector에 넣어줌.
2. 도로 경로 길이 0 -> 딕스트라가 경로길이>=0인 경우를 커버하는 거 같아 특별히 신경을 안 썼습니다.
3. 도로 길이 최대값 -> 문제에 특별히 명시되지 않았는데, 혹시 모를 overflow를 대비해 딕스트라에서 중간 cost(cost_so_far)는 int64_t에 저장했습니다.
4. 뭐가 또 있을까요?;;; 뭔가 빼먹은게 분명한데 말이죠;;

~~~ c++
#include
#include

int C, N, M;
//A,B 도시 사이 코스트 C, A<<16+B --> C
map Link;
#define KEY(x,y) ((x<<16)+y)
int64_t cost_so_far[10000];
typedef vector V;

struct Node {
Node(int n) :
n(n) {
}
int n;
bool operator<(const Node &t) const {
return cost_so_far[n] > cost_so_far[t.n];
}
};

int64_t f(V neighbors[]) {
priority_queue q;
cost_so_far[0] = 0, q.push(Node(0));
for (int i = 1; i < N; ++i)
cost_so_far[i] = 10e17, q.push(i); // 두도시 사이의 default cost==10e17

while (q.size()) {
    Node u = q.top();
    q.pop();
    if (u.n == N - 1)
        break;
    for (V::iterator it = neighbors[u.n].begin();
            it != neighbors[u.n].end(); ++it) {
        int64_t t = cost_so_far[u.n] + Link[KEY(u.n, *it)];
        if (t < cost_so_far[*it])
            cost_so_far[*it] = t;
    }
}
return cost_so_far[N - 1];

}

int main() {
scanf("%d", &C);
while (--C >= 0) {
// 이웃 도시 정보 저장 0도시 의 이웃 도시가 1,2,3이라면, neighbors[0] --> Vector[1,2,3]
V neighbors[10000];
scanf("%d%d", &N, &M);
for (int i = 0; i < M; ++i) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if (Link.find(KEY(a, b)) == Link.end() //아직 읽지 않은 경로거나
|| (Link.find(KEY(a, b)) != Link.end() && Link[KEY(a, b)] > c)) { // 읽었지만, 짧다면
Link[KEY(a, b)] = Link[KEY(b, a)] = c;
neighbors[a].push_back(b), neighbors[b].push_back(a);
}
}
printf("%I64d\n", f(neighbors));
}
}

</spoiler>