ZZULI - 小P上考场(最短路)

题目链接:http://acm.zzuli.edu.cn/problem.php?id=1524
时间限制: 1 Sec 内存限制: 128 MB

题目描述

小P一觉醒来发现天已经亮了。今天是程序设计大赛的日子，小P需要尽快赶往考场。 小P家在a号路口，他会告诉你哪些路口是相联通的，距离是多少。赛场在b号路口，该市道路没有单行道。 小P想让你帮他规划到考场的路线，他希望找到这条最短的路线以用最短时间抵达考场。

输入

第一行四个整数n，m，a，b (1<=n<=2500 ,1<=m<=6200 ,1<=a,b<=n ) ，n表示有n个路口，m表示有m条路，每两个路口之间连通算一条路，接下来m行，每行三个数，x，y，c代表x路口到y路口之间有一条路距离为c

输出

一个数，小P家到比赛现场的距离。

样例输入

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

样例输出

7

提示

1<=n<=2500
1<=m<=6200
1<=a,b<=n

解题思路

最短路走一波。。。

#include <queue> #include <cstdio> #include <cstring> using namespace std; struct edge { int u, v, w; }e[12405]; int n, cnt; int f[2505], vis[2505], dis[2505]; void Add(int u, int v, int w) { e[++cnt] = (edge){f[u], v, w}; f[u] = cnt; } void Spfa(int s) { int t, u; queue <int> Q; Q.push(s); dis[s] = 0; vis[s] = 1; while (!Q.empty()) { t = Q.front(); Q.pop(); vis[t] = 0; for (int i = f[t]; i; i = e[i].u) { u = e[i].v; if (dis[u] > dis[t] + e[i].w) { dis[u] = dis[t] + e[i].w; if (!vis[u]) { vis[u] = 1; Q.push(u); } } } } } int main() { int m, s, t, u, v, w; while (~scanf("%d%d%d%d", &n, &m, &s, &t)) { memset(f, 0, sizeof(f)); memset(vis, 0, sizeof(vis)); memset(dis, 0x3f, sizeof(dis)); for (int i = 0; i < m; i++) { scanf("%d%d%d", &u, &v, &w); Add(u, v, w); Add(v, u, w); } Spfa(s); printf("%d\n", dis[t]); } return 0; }