hdu-2544-最短路(SPFA)

简介: hdu-2544-最短路(SPFA)




最短路

Time Limit : 5000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 62   Accepted Submission(s) : 40

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<=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      

 


Source

UESTC 6th Programming Contest Online

 


题目分析:

简单纯粹的最短路径,刚学了邻接表和SPFA,就用建表写了一个SPFA很有写深搜的感觉

很好用。不解释看邻接表详解      邻接表详解


#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define maxn 100+10
#define maxm 20000+10
#define INF 0x3f3f3f3f
using namespace std;
struct Edge
{
  int from,to,val,next;
};
Edge  edge[maxm];
int head[maxn],edgenum;
int n,m;
void addEdge(int u,int v,int w)
{
  Edge E={u,v,w,head[u]};
  edge[edgenum]=E;
  head[u]=edgenum++;
}
void init()
{
  edgenum=0;
  memset(head,-1,sizeof(head));
}
int dist[maxn];
int mark[maxn];
void SPFA(int sx)
{
  queue<int> q;
  memset(dist,INF,sizeof(dist));
  memset(mark,0,sizeof(mark));
  q.push(sx);
  dist[sx]=0;
  mark[sx]=1;
  while(!q.empty())
  {
    int u=q.front();
    q.pop();
    mark[u]=0;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
      int v=edge[i].to;
      if(dist[v]>dist[u]+edge[i].val)
      {
        dist[v]=dist[u]+edge[i].val;
        if(!mark[v])
        {
          mark[v]=1;
          q.push(v);
        }
      }
    }
  }
  printf("%d\n",dist[n]);
}
void getMap()
{
  int a,b,c;
  while(m--)
  {
    scanf("%d%d%d",&a,&b,&c);
      addEdge(a,b,c);
      addEdge(b,a,c);
  }
}
/*void get_map()
{
  for(int u=1;u<=n;u++)
  {
     printf("%d :",u);
     for(int i=head[u];i!=-1;i=edge[i].next)
     {
      printf("%d ",edge[i].to);
     }
     printf("\n");
  }
}*/  这里是输出邻接表
int main()
{
  while(scanf("%d%d",&n,&m),n||m)
  {
    init();
    getMap();
    //get_map();
    SPFA(1);
  }
  return 0;
}




目录
相关文章
|
6月前
|
机器学习/深度学习 算法 数据挖掘
PyTabKit:比sklearn更强大的表格数据机器学习框架
PyTabKit是一个专为表格数据设计的新兴机器学习框架,集成了RealMLP等先进深度学习技术与优化的GBDT超参数配置。相比传统Scikit-Learn,PyTabKit通过元级调优的默认参数设置,在无需复杂超参调整的情况下,显著提升中大型数据集的性能表现。其简化API设计、高效训练速度和多模型集成能力,使其成为企业决策与竞赛建模的理想工具。
175 12
PyTabKit:比sklearn更强大的表格数据机器学习框架
|
7月前
|
JSON 监控 API
1688商品列表API接口指南
1688 商品列表 API 可帮助开发者和商家获取商品基本信息(如 ID、名称、价格等)、支持筛选排序(类目、价格、销量等条件)、分页查询及指定店铺商品获取,便于商品管理与竞品分析。调用流程包括:注册账号创建应用以获取 App Key 和 App Secret、生成签名确保请求合法性、构造请求参数(含 app_key、sign 等)、发送 HTTP 请求并处理 JSON 响应数据。
269 19
|
人工智能 数据可视化 定位技术
DataV AI助手小技巧-如何制作PPT数据地图
“数据地图”是PPT汇报地区业务数据的最佳形式之一;以往制作数据地图需要用户有一定的编程和数据处理基础,制作门槛较高;随着DataV整合通义千问大模型能力之后,不懂编程和设计的用户也可以借助AI助手“零代码”制作数据地图,真正实现了人人可用的地图数据可视化。 进入大模型AI时代,人人可以变成职场跨界多面手!
11848 3
DataV AI助手小技巧-如何制作PPT数据地图
|
SQL 关系型数据库 MySQL
深入探索MySQL索引策略
本文旨在深入探讨MySQL(8.0.26)数据库中索引的设计与优化方法。
|
Web App开发 JSON JavaScript
Chrome 插件各模块之间的消息传递
Chrome 插件各模块之间的消息传递 一、消息传递 1. 消息传递分类 Chrome 插件的 Action、Background 和 content_script 三个模块之间的信息传输 插件和插件之间的信息传输 网页向插件进行信息传输 与原生应用进行消息传递
731 0
|
存储 传感器 编解码
【Camera基础(二)】摄像头驱动原理和开发&&V4L2子系统驱动架构
【Camera基础(二)】摄像头驱动原理和开发&&V4L2子系统驱动架构
|
监控 前端开发 Java
SpringBoot与SpringMVC有哪些区别?
SpringBoot和SpringMVC是Java开发中常用的两个框架,它们都是由Spring框架所提供的,但在功能和使用方式上有着一些区别。
1286 2
|
JavaScript 前端开发 存储
JavaScript高级笔记-coderwhy版本(四)
JavaScript高级笔记-coderwhy版本
198 0
|
存储 机器学习/深度学习 人工智能
基于Megatron-Core的稀疏大模型训练工具:阿里云MoE大模型最佳实践
随着大模型技术的不断发展,模型结构和参数量级快速演化。大模型技术的应用层出不穷。大模型展现惊人效果,但训练和推理成本高,一直是巨大挑战。模型稀疏化能降低计算和存储消耗。近期以Mixtral为代表的MoE(多专家混合)大模型证明了稀疏MoE技术能大幅降低计算量、提升推理速度,模型效果甚至超过同规模稠密模型。阿里云PAI和NVIDIA团队深入合作,基于Megatron-Core MoE框架,解决了MoE大模型训练落地时会遇到的可拓展性、易用性、功能性以及收敛精度等核心问题,在下游任务上取得了很好的模型效果。
|
弹性计算 运维 Kubernetes
SpringCloud 应用在 Kubernetes 上的最佳实践 — 线上发布(可回滚)
本篇是《SpringCloud 应用在 Kubernetes 上的最佳实践》系列文章的第七篇,主要介绍了新功能上线时,如何尽快减少对线上用户的影响?发布系统需要提供回滚到前一个或前几个版本的能力,达到快速恢复线上业务的目的。
2884 80
SpringCloud 应用在 Kubernetes 上的最佳实践 — 线上发布(可回滚)