[hihoCoder] #1093 : 最短路径·三:SPFA算法_weixin_34082854的博客-程序员秘密

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

万圣节的晚上,小Hi和小Ho在吃过晚饭之后,来到了一个巨大的鬼屋!

鬼屋中一共有N个地点,分别编号为1..N,这N个地点之间互相有一些道路连通,两个地点之间可能有多条道路连通,但是并不存在一条两端都是同一个地点的道路。

不过这个鬼屋虽然很大,但是其中的道路并不算多,所以小Hi还是希望能够知道从入口到出口的最短距离是多少?

提示:Super Programming Festival Algorithm。

输入

每个测试点(输入文件)有且仅有一组测试数据。

在一组测试数据中:

第1行为4个整数N、M、S、T,分别表示鬼屋中地点的个数和道路的条数,入口(也是一个地点)的编号,出口(同样也是一个地点)的编号。

接下来的M行,每行描述一条道路:其中的第i行为三个整数u_i, v_i, length_i,表明在编号为u_i的地点和编号为v_i的地点之间有一条长度为length_i的道路。

对于100%的数据,满足N<=10^5,M<=10^6, 1 <= length_i <= 10^3, 1 <= S, T <= N, 且S不等于T。

对于100%的数据,满足小Hi和小Ho总是有办法从入口通过地图上标注出来的道路到达出口。

输出

对于每组测试数据,输出一个整数Ans,表示那么小Hi和小Ho为了走出鬼屋至少要走的路程。

样例输入
5 10 3 5
1 2 997
2 3 505
3 4 118
4 5 54
3 5 480
3 4 796
5 2 794
2 5 146
5 4 604
2 5 63
样例输出
172

 

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 #include <algorithm>
 5 #include <climits>
 6 using namespace std;
 7 
 8 const int INF = 1e9;
 9 
10 struct node {
11     int idx;
12     int len;
13     node(int _idx = 0, int _len = 0) : idx(_idx), len(_len){}
14 };
15 
16 int N, M, S, T;
17 vector<vector<node>> graph;
18 vector<int> dist;
19 
20 void solve() {
21     vector<int> visit(N+1, false);
22     //priority_queue<int, vector<int>, greater<int>> heap;
23     queue<int> heap;
24     dist[S] = 0;
25     heap.push(S);
26     visit[S] = true;
27     while (!heap.empty()) {
28         //int u = heap.top();
29         int u = heap.front();
30         heap.pop();
31         visit[u] = false;
32         for (int i = 0; i < graph[u].size(); ++i) {
33             int v = graph[u][i].idx;
34             if (dist[v] > dist[u] + graph[u][i].len) {
35                 dist[v] = dist[u] + graph[u][i].len;
36                 if (!visit[v]) {
37                     heap.push(v);
38                     visit[v] = true;
39                 }
40             }
41         }
42     }
43     cout << dist[T] << endl;
44 }
45 
46 int main() {
47     while (cin >> N >> M >> S >> T) {
48         graph.assign(N+1, vector<node>(0));
49         dist.assign(N+1, INF);
50         int u, v, len;
51         for (int i = 1; i <= M; ++i) {
52             cin >> u >> v >> len;
53             graph[u].push_back(node(v, len));
54             graph[v].push_back(node(u, len));
55         }
56         solve();
57     }
58     return 0;
59 }

 堆优化的Dijkstra算法。总体来说还是SPFA算法更好写一点。不过Dijsktra算法可以提前输出,只到轮到点T,直接输出即可。

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int INF = 1e9;
 8 
 9 struct edge {
10     int idx;
11     int dist;
12     edge(int _idx, int _dist) : idx(_idx), dist(_dist) {}
13 };
14 
15 struct cmp {
16     bool operator () (const edge &a, const edge &b) { return a.dist > b.dist; }
17 };
18 
19 int N, M, S, T;
20 vector<vector<edge>> graph;
21 
22 void solve() {
23     priority_queue<edge, vector<edge>, cmp> heap;
24     vector<int> dist(N + 1, INF);
25     vector<bool> visit(N + 1, false);
26     dist[S] = 0;
27     visit[S] = true;
28     for (int i = 0; i < graph[S].size(); ++i) {
29         auto v = graph[S][i];
30         dist[v.idx] = min(dist[v.idx], v.dist);
31         heap.push(edge(v.idx, dist[v.idx]));
32     }
33     while (!heap.empty()) {
34         auto u = heap.top();
35         heap.pop();
36         if (u.idx == T) {
37             cout << u.dist << endl;
38             return;
39         }
40         if (visit[u.idx]) continue;
41         visit[u.idx] = true;
42         for (int i = 0; i < graph[u.idx].size(); ++i) {
43             auto v = graph[u.idx][i];
44             if (!visit[v.idx] && dist[v.idx] > dist[u.idx] + v.dist) {
45                 dist[v.idx] = dist[u.idx] + v.dist;
46                 heap.push(edge(v.idx, dist[v.idx]));
47             }
48         }
49     }
50     cout << "-1" << endl;
51 }
52 
53 int main() {
54     while (cin >> N >> M >> S >> T) {
55         int u, v, len;
56         graph.resize(N + 1);
57         for (int i = 0; i < M; ++i) {
58             cin >> u >> v >> len;
59             graph[u].push_back(edge(v, len));
60             graph[v].push_back(edge(u, len));
61         }
62         solve();
63     }
64     return 0;
65 }

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_34082854/article/details/86049187

智能推荐

c语言 约瑟夫,C语言解决约瑟夫问题详解的代码_胡厨厨的博客-程序员秘密

将开发过程中比较重要的一些内容做个收藏,下面的内容是关于C语言解决约瑟夫问题详解的内容,希望能对码农有帮助。#pragma once#includeclass PRO{private:public:~PRO();};#include"Josephus_pro.h"#includeusing namespace std;PRO::PRO(int tol_num,int sg_num,int rema...

Linux 查看服务器cpu信息常用命令大全_没有络腮胡的博客-程序员秘密_linux查看服务器cpu

查看物理CPU的个数cat /proc/cpuinfo |grep “physical id”|sort |uniq|wc -l查看逻辑CPU的个数cat /proc/cpuinfo |grep “processor”|wc -l查看CPU是几核cat /proc/cpuinfo |grep “cores”|uniq查看当前操作系统内核信息uname -a查看当前操作系统发行版信息cat /etc/issue查看逻辑CPU个数, 同时查看CPU型号cat /pro

unity-ECS-DOTS笔记_一兔子先生一的博客-程序员秘密_unity dots 报错

EntityComponentSystemJobC#虽然支持Thread,但是在Unity中只能处理数据,例如:网络消息、下载。如果想在Thread中调用Unity的API那是不行的。job中使用主线程API会报错:“UnityException: GetKeyInt can only be called from the main thread.” protected override JobHandle OnUpdate(JobHandle inputDeps) {

SSH框架整合的一些步骤整理(二)_星逝星魂的博客-程序员秘密

这一章讲spring和struts2的整合一、为项目添加struts2的功能添加后出现struts配置文件(等一下会配置):二、修改Web.xml文件 SpringHibernateStruts index.jsp <!-- 服务器启动时,通过监听器初始化Spring的配置环境 监听器,默认加载文件是:/WEB-INF/ap

JAVA版村庄哨塔种子_我的世界奇妙种子:掠夺者哨塔骑在沙漠神殿上,村民:绝了!..._Alfred Cheng的博客-程序员秘密

伪萌新还是没有大家厉害,因为粉丝们找到的种子实在是太“奇妙”了!本期就分享两个粉丝推荐种子(一个手机版,一个Java版)。看完后估计你会忍不住去探索。骑在沙漠神殿上的掠夺者哨塔,村民:绝了!手机版种子1:这个种子的出生点很一般,但是在这个种子的远方却隐藏了一个大秘密。在坐标98 ~ 499处生成了一座掠夺者哨塔。并且这座掠夺者哨塔和普通的哨塔不一样!因为它实在是太高了。直耸云霄,你看图中的这个仰视...

Mysql一个字段存储多个url_MySql一个字段用;隔开,存储了多个照片路径,如何用JS显示所有图片在页面上。..._weixin_39781186的博客-程序员秘密

[email protected]:/var/lib/mysql-files# for i in `seq 1 100`; do cp 微信图片_20190711095019.jpg "$i".jpg;done;[email protected]:/var/lib/mysql-files# ls100.jpg 17.jpg 25.jpg 33.jpg 41.jpg 4.jpg 58.jpg 66.jpg 74.j...

随便推点

鸿蒙初体验:从安装到第一个程序 Hello HarmonyOS_文化沙漠麦七的博客-程序员秘密

华为鸿蒙OS 2.0就不多介绍了一、源码和应用下载地址鸿蒙的源码地址:https://openharmony.gitee.com华为开发者联盟:https://developer.huawei.com/consumer/cn官方文档:https://developer.harmonyos.com/cn/docs/documentation/doc-guides/ui-java-layout-dependentlayout-0000001050729536二、安装与运行1.运行环境要求DevEc

使用ASM操作Java字节码,实现AOP原理_wangxin0314的博客-程序员秘密

本文通过一个的例子来实现:使用ASM动态生成Java字节码文件(.class) 或者 加载字节码后动态修改字节码,添加我们需要执行的代码,来模拟实现spring AOP。年底了,也没心情抠字了,把写demo包含的几个类代码直接贴出来吧,代码拷贝下来后可以直接使用,不会有什么其他错误。 使用 asm-5.0.3.jar demo工程的package为com.shanhy.demo.a

虚拟专家座谈会:迈向云开发_wuhaung1013的博客-程序员秘密

开发者正在不断体验多种不同的云环境。当在云中工作时,开发者应如何改变他们的思考方式?是否有某些云环境更适合于刚准备入门的开发者?而那些目前尚未涉及云开发的开发者们又如何在此领域获得相应技能呢?\u0026#xD;为了回答这些问题,InfoQ就云开发的现状、推荐工具和反面模式与三位意见领袖进行了交流。我们的专家组成员是:\u0026#xD;Adron Hall,通晓多种语言的码农和开发人员布道师。\...

supersocket+c#+oracle,C#SuperSocket服务器的简易实现_蓝青又出青的博客-程序员秘密

C#SuperSocket服务器的简易实现发布时间:2019-04-26 22:48,浏览次数:3543, 标签:SuperSocket上一篇文章我们使用原生的socket分别实现了服务器和客户端,本篇文章使用SuperSocket来开发实现服务器,之前也介绍了SuperSocket是一个轻量级, 跨平台而且可扩展的 .Net/Mono Socket 服务器程序框架。你无须了解如何使用 Socke...

supersocket缓冲区_关于supersocker的数据传输中遇到的问题_weixin_39592240的博客-程序员秘密

最近在学socket,在使用socket时数据的传输与接口都是byte,所以文本与文件的传输只要对传过来的byte处理好就可以。但是在supersocket上,我却花费了很长的时间。原因如下:1、从客户端传来的byte都会处理成string,在开始接触supersocket时发现对于文字的传输很方便,但是到了文件的传输时我才发现,传过来的byte都会转化为string,这让我很是烦恼,在经过排查才...

深入浅出学习Struts框架(十二)-分析Struts框架实例7_long_yu2的博客-程序员秘密

上一篇博客主要是讲解ActionServlet中的一个方法processActionForm,当我们在截取字符串,再根据字符串取得ActionMapping之后,我们就要用利用ActionMapping来创建ActionForm,并且把ActionForm放到request或session中管理。获得ActionForm之后,我们就要将ActionForm中的数据放到Mapping中,以便实例化...

推荐文章

热门文章

相关标签