小木乃伊到我家 dijkstra + 链表 + 优先队列

https://ac.nowcoder.com/acm/contest/96/E?&headNav=www&headNav=acm

题目描述

AA的欧尼酱qwb是个考古学家，有一天qwb发现了只白白圆圆小小的木乃伊，它是个爱哭鬼却很努力。qwb想把这么可爱的小木乃伊送给
AA，于是便找上了快递姐姐，这下可让快递姐姐犯愁了，因为去往AA家的路实在太难走了（甚至有可能没有路能走到AA家），快递姐姐
找上聪明的ACMer，想请你帮忙找出最快到达AA家的路，你行吗？

输入描述:

第一行输入两个整数n和m（2<=n<=m<=200000），分别表示有n座城市和m条路，城市编号为1~n（快递姐姐所在城市为1，AA所在城市为n）。
接下来m行，每行输入3个整数u,v,w（u,v<=n，w<=100000），分别表示城市u和城市v之间有一条长为w的路。

输出描述:

输出结果占一行，输出快递姐姐到达AA家最短需要走多远的路，如果没有路能走到AA家，则输出“qwb baka”（不用输出双引号）。

输入例子:

输出例子:

-->

示例1

输入

复制

输出

复制

题解：$a[i] = j$ 代表第 $i$ 条边的起点是 $j$; $b[i] = j$ 代表第 $i$ 条边的终点是 $j$; $c[i] = j$ 代表第 $i$ 条边的长度是 $j$; $nx[i]$ 代表的是第 $i$ 条边的下一条边是 $j$ 边; $h[i] = j$ 代表以 $i$ 开始的边是第 $j$ 边

代码：

#include <bits/stdc++.h>

using namespace std;

long long INF = 1e18;

const int Node= 200000 + 10;

const int Edge = (200000 + 10) * 2;

int n, m, s;

long long dis[Node];

int h[Node], a[Edge], b[Edge], nx[Edge], edgeCount;

long long c[Edge];

void init() {

  s = 1;

  edgeCount = 0;

  for (int i = 1; i <= n; i++) {

    dis[i] = INF;

    h[i] = -1;

  }

  dis[s] = 0;

}

void add(int aa, int bb, long long cc) {

  a[edgeCount] = aa;

  b[edgeCount] = bb;

  c[edgeCount] = cc;

  nx[edgeCount] = h[aa];

  h[aa] = edgeCount;

  edgeCount++;

}

void input() {

  for (int i = 1; i <= m; i++) {

    int aa, bb;

    long long cc;

    scanf("%d%d%lld", &aa, &bb, &cc);

    add(aa, bb, cc);

    add(bb, aa, cc);

  }

}

void dijkstra() {

  priority_queue<pair<long long, int>> q;

  q.push(make_pair(0, s));

  while (!q.empty()) {

    pair<long long, int> tp = q.top();

    q.pop();

    int d = -tp.first;

    int v = tp.second;

    for (int i = h[v]; i != -1; i = nx[i]) {

      if (dis[v] + c[i] < dis[b[i]]) {

        dis[b[i]] = dis[v] + c[i];

        q.push(make_pair(-dis[b[i]], b[i]));

      }

    }

  }

}

int main() {

  while (~scanf("%d%d", &n, &m)) {

    if (n == 0 && m == 0) {

      break;

    }

    init();

    input();

    dijkstra();

    if (dis[n] != INF) {

      printf("%lld\n", dis[n]);

    } else {

      printf("qwb baka\n");

    }

  }

  return 0;

}

神仙代码昨天差不多看了半天脑阔疼学到了

巴特西