hdu 2544(SPFA)
2024-10-20 16:06:12
最短路
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 51083 Accepted Submission(s): 22464
Problem 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&
lt;=N,1<=C<=1000),表示在路口A与路口B之间有一条路,我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。
入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店
所在地,标号为N的路口是赛场所在地,M则表示在成都有几条路。N=M=0表示输入结束。接下来M行,每行包括3个整数A,B,C(1<=A,B&
lt;=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
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
Sample Output
3
2
2
一直没用过SPFA,打个水题练下手
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <queue>
using namespace std;
const int N = ;
const int M = ;
const int INF = ;
struct Edge{
int v,w,next;
}edge[M*];
int head[N];
bool vis[N];
int dis[N],time[N];
int n,m;
bool spfa(int s){
queue<int> q;
memset(vis,false,sizeof(vis));
memset(time,,sizeof(time));
for(int i=;i<=n;i++){
dis[i]=(i==s)?:INF;
}
q.push(s);
time[s]++;
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = false;
for(int k = head[u];k!=-;k=edge[k].next){
int v = edge[k].v,w = edge[k].w;
if(dis[u]+w<dis[v]){
dis[v] = dis[u]+w;
if(!vis[v]){
vis[v] = true;
time[v]++;
q.push(v);
if(time[v]>n) return false;
}
}
}
}
return true;
}
void addedge(int u,int v,int w,int &k){
edge[k].v = v,edge[k].w=w,edge[k].next = head[u],head[u]=k++;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF,(n+m))
{
memset(head,-,sizeof(head));
int tot=,u,v,w;
for(int i=;i<m;i++){
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w,tot);
addedge(v,u,w,tot);
}
spfa();
printf("%d\n",dis[n]);
}
return ;
}
最新文章
- sql 连接查询的区别 inner,left,right,full
- MVC 架构
- Count and Say leetcode
- windows下如何对mysql进行整裤备份
- Hadoop分布式配置
- Style 的优先级
- Javascript个人理解
- 利用python进行数据分析之数据规整化
- nodeJS实战:自定义模块与引入,不同模块的函数传递及回调处理,exports与module.exports(基于nodejs6.2.0)
- Swing-选项卡面板JTabbedPane-入门
- MongoDB集群搭建-副本集
- css控制UL LI 的样式详解(推荐)
- pygame学习
- Go Socket实现简单的HttpServer
- WPF DataGrid分页功能实现代码
- JavaScript原型之路
- Linux查看CPU和内存的配置信息
- 无刷新文件上传 利用iframe实现
- Excel 2007表格内输入http取消自动加上超链接的功能
- 【CSS3】特殊的属性归纳(二)
热门文章
- W/System.err: at android.view.ViewConfiguration.get(ViewConfiguration.java:369)
- Android stadio 工具使用
- easyui js拼接html,class属性失效的问题
- 论如何入门地使用vscode
- @property后面可以有哪些修饰符?
- 一个python的文件对比脚本
- 使用node构建一个自己的服务器
- 孤荷凌寒自学python第四十九天继续研究跨不同类型数据库的通用数据表操作函数
- 1004 Counting Leaves (30 分)(树的遍历)
- HS 光流法详解