HDU - 2544 最短路（SPFA板题）

2024-02-17 12:48

本文主要是介绍HDU - 2544 最短路（SPFA板题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

Input

输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。

Output

对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间
Sample Input
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

Sample Output

3
2

Solution

SPFA板题，利用邻接表存储图的结构，可以判断负环。

#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <vector>
using namespace std;
const int max_edge = 11111;
const int max_vertex = 111;
//N为顶点数 M为边数 Dis为到每个顶点的最短距离
int N, M, Dis[max_vertex];
int num_v[max_vertex]; //判断负环
struct Edge
{int u, v, w;Edge(int _v, int _w) : v(_v), w(_w){};
};
vector<Edge> Adj[max_edge]; //邻接表存储图的结构
bool SPFA(int start)
{bool visit[max_vertex];memset(visit, 0, sizeof(visit));memset(Dis, 0x3f, sizeof(Dis));memset(num_v, 0, sizeof(num_v));queue<int> Q;Q.push(start);num_v[start]++;Dis[start] = 0;visit[start] = true;while ((!Q.empty())){int u = Q.front();Q.pop();visit[u] = false;for (int i = 0; i < Adj[u].size(); i++) //遍历每一个顶点的各个边{int v = Adj[u][i].v;int dis = Adj[u][i].w;if (Dis[u] + dis < Dis[v]) //原点到u的距离+u到v的距离 < 原点到v的距离{Dis[v] = Dis[u] + dis;if (!visit[v]) //v不在队列中{Q.push(v);visit[v] = true;num_v[v]++;if (num_v[v] >= N) //判断负环return false;}}}}return true;
}
int main()
{// freopen("in.txt", "r", stdin);while (~scanf("%d%d", &N, &M) && (N || M)){for (int i = 0; i < max_vertex; i++)Adj[i].clear();for (int i = 0; i < M; i++){int u, v, w; //建立邻接表scanf("%d%d%d", &u, &v, &w);Adj[u].push_back(Edge(v, w));Adj[v].push_back(Edge(u, w));}SPFA(1); //参数为起点printf("%d\n", Dis[N]);}return 0;
}