2018年长沙理工大学第十三届程序设计竞赛 E 小木乃伊到我家 【最短路】

木乃伊到我家 【最短路】"/>

2018年长沙理工大学第十三届程序设计竞赛 E 小木乃伊到我家 【最短路】

时间限制：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_backusing 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");elseprintf("%lld\n", v[n]);}
}

转载于:.html