题目
题目描述
贝茜在谷仓外的农场上，她想回到谷仓，在第二天早晨农夫约翰叫她起来挤奶之前尽可能多地睡上一觉．由于需要睡个好觉，贝茜必须尽快回到谷仓．农夫约翰的农场上有N(2≤N≤1000)个路标，每一个路标都有唯一的编号（1到N）．路标1是谷仓，路标N是贝茜一整天呆在那里的果树园．农场的所有路标之间共有T(1≤T≤2000)条不同长度的供奶牛走的小路（无方向）．贝茜对她识别方向的能力不是很自信，所以她每次总是从一条小路的头走到尾，再以这条路的尾作为下一条路的头开始走． 现给出所有路标之间的小路，要求输出贝茜回到谷仓的最短路程（每组输入数据都保证有解）．
输入
第1行：2个整数T和N．
第2到T+1行：每行用空格隔开的三个整数描述一条小路．前两个整数是这条小路的尾和头，
第三个整数是这条小路的长度（不大于100）．
输出
一个整数，表示贝茜从路标N到路标1所经过的最短路程
样例输入
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100
样例输出
90
分析
spfa裸题。
链式前向星存图，spfa跑一遍完事。
上代码。
#include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; const int N = 10010; const int M = 40010; int n, m; int head[N], nex[M], to[M], val[M], ce; void add(int u, int v, int w) { to[++ce] = u; nex[ce] = head[v]; head[v] = ce; val[ce] = w; to[++ce] = v; nex[ce] = head[u]; head[u] = ce; val[ce] = w; } int d[N]; bool used[N]; queue<int> q; void spfa(int s) { memset(d, 0x3f, sizeof d); d[s] = 0; q.push(s); used[s] = true; while(!q.empty()) { int u = q.front(); q.pop(); used[u] = false; for(int i=head[u]; i; i=nex[i]) { int v = to[i], w = val[i]; if(d[u] + w < d[v]) { d[v] = d[u] + w; if(!used[v]) { used[v] = true; q.push(v); } } } } } int main() { scanf("%d%d", &m, &n); for(int i=1; i<=m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); add(u, v, w); } spfa(1); printf("%d ", d[n]); return 0; }