时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld 题目描述 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
思路 数据好像没那么大。。 用广搜 就能搜了
但是要注意的是 城市之间 有一条路 是双向的 所以在压入路的时候 要压入两次
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; typedef pair <int, ll> pil; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const ll llINF = 0x3f3f3f3f3f3f3f3f; const int maxn = 2e5 + 5; const int MOD = 1e9; vector <pil> G[maxn]; ll v[maxn]; int n, m; struct node { int y; ll fee; }; void bfs() { int len = G[1].size(); node tmp; queue <node> q; for (int i = 0; i < len; i++) { tmp.y = G[1][i].first; tmp.fee = G[1][i].second; v[tmp.y] = min(v[tmp.y], tmp.fee); q.push(tmp); } while (!q.empty()) { node u = q.front(), w; q.pop(); len = G[u.y].size(); for (int i = 0; i < len; i++) { w.y = G[u.y][i].first; w.fee = u.fee + G[u.y][i].second; if (w.fee <= v[w.y]) { q.push(w); v[w.y] = w.fee; } } } } int main() { while (~scanf("%d%d", &n, &m)) { CLR(v, 0x3f); G->clear(); int x, y; ll c; for (int i = 0; i < m; i++) { scanf("%d%d%lld", &x, &y, &c); if (x > y) swap(x, y); G[x].pb(pii(y, c)); G[y].pb(pii(x, c)); } bfs(); if (v[n] == llINF) printf("qwb baka\n"); else printf("%lld\n", v[n]); } }转载于:https://www.cnblogs.com/Dup4/p/9433097.html
