[HDOJ6386] Age of Moyu (最短路)

链接：http://acm.hdu.edu.cn/showproblem.php?pid=6386

意思就是地铁换乘，问你怎么坐，换乘次数最少

这题数据水了，我的代码放过去去了。正解应该是维护到点的每个最短的距离的线路，然后更新的时候从这个线路中去找有没有存在的。我这里只是维护了最短路的上一个线路（看来是没有二条以上路径相同但是线路不同的数据），最后正着倒着各跑一次dijkstra取min的。。

#include <bits/stdc++.h>
using namespace std;

using LL = long long;
typedef tuple<LL, LL, LL> TP;
typedef struct Edge {
  LL v, w, next;
}Edge;
const LL maxn = 100100;
const LL maxm = 2001000;
const LL inf = 0x7f7f7f7f;
LL n, m, ee;
LL d[maxn];
LL head[maxn];
Edge e[maxm];
priority_queue<TP, vector<TP>, greater<TP>> pq;

void init() {
  ee = 0;
  memset(head, -1, sizeof(head));
}

void adde(LL u, LL v, LL w) {
  e[ee].v = v; e[ee].w = w; e[ee].next = head[u]; head[u] = ee++;
  e[ee].v = u; e[ee].w = w; e[ee].next = head[v]; head[v] = ee++;
}

LL dijkstra(LL s, LL t) {
  memset(d, 0x7f, sizeof(d));
  d[s] = 0;
  LL pre_cost, pre_id, from;
  pq.push(TP(0, -1, s));
  while(!pq.empty()) {
    tie(pre_cost, pre_id, from) = pq.top(); pq.pop();
    if(d[from] < pre_cost) continue;
    for(LL i = head[from]; ~i; i=e[i].next) {
      LL v = e[i].v, w = e[i].w;
      LL cost, cur_id;
      if(w == pre_id) {
        cost = 0; cur_id = w;
      }
      else {
        cost = 1; cur_id = w;
      }
      if(cost + d[from] < d[v]) {
        d[v] = cost + d[from];
        pq.push(TP(d[v], cur_id, v));
      }
    }
  }
  return d[t];
}

LL find(LL x) {
  return x == d[x] ? x : d[x] = find(d[x]);
}

signed main() {
  // freopen("in", "r", stdin);
  LL u, v, w;
  while(~scanf("%I64d%I64d",&n,&m)) {
    init();
    for(LL i = 1; i <= n; i++){
      d[i] = i;
    }
    for(LL i = 0; i < m; i++) {
      scanf("%I64d%I64d%I64d",&u,&v,&w);
      d[find(u)] = find(v);
      adde(u, v, w);
    }
    if(find(1) != find(n)) {
      printf("-1\n");
      continue;
    }
    printf("%I64d\n", min(dijkstra(n, 1), dijkstra(1, n)));
  }
  return 0;
}