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

队列"/>

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

?&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

输入

复制

4 4
1 2 1
2 3 2
3 4 3
2 3 1

输出

复制

5

题解：$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;
}

　　

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

转载于:.html