[kuangbin带你飞]专题四 最短路练习 -A - Til the Cows Come Home-程序员宅基地

技术标签: [kuangbin带你飞]专题四 最短路练习  acm  

Til the Cows Come Home
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 41196   Accepted: 13984

Description

Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her beauty sleep, so she wants to get back as quickly as possible. 

Farmer John's field has N (2 <= N <= 1000) landmarks in it, uniquely numbered 1..N. Landmark 1 is the barn; the apple tree grove in which Bessie stands all day is landmark N. Cows travel in the field using T (1 <= T <= 2000) bidirectional cow-trails of various lengths between the landmarks. Bessie is not confident of her navigation ability, so she always stays on a trail from its start to its end once she starts it. 

Given the trails between the landmarks, determine the minimum distance Bessie must walk to get back to the barn. It is guaranteed that some such route exists.

Input

* Line 1: Two integers: T and N 

* Lines 2..T+1: Each line describes a trail as three space-separated integers. The first two integers are the landmarks between which the trail travels. The third integer is the length of the trail, range 1..100.

Output

* Line 1: A single integer, the minimum distance that Bessie must travel to get from landmark N to landmark 1.

Sample Input

5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100

Sample Output

90

Hint

INPUT DETAILS: 

There are five landmarks. 

OUTPUT DETAILS: 

Bessie can get home by following trails 4, 3, 2, and 1.


使用bellman-ford水过,63ms

[bellman-ford,松弛,松弛,松弛。就是一根无限远的绳子变短了,不断的蹦蹦的松弛了,233333,从紧绷的小女生,变成老太婆,就是bellman-ford啦]


code:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#define INF 1<<29
#define MAXp 2005
using namespace std;
typedef long long ll;
typedef struct {
	int a, b, value;
}Edge;

ll n, m;
Edge edge[MAXp];

void solve()
{
	ll d[1005];
	for (ll i = 2; i <= n; i++) d[i] = INF;
	d[1] = 0;

	while (true)
	{
		bool update = false;
		for (ll i = 1; i <= m; i++)
		{
			if (d[edge[i].a] > d[edge[i].b] + edge[i].value)
			{
				d[edge[i].a] = d[edge[i].b] + edge[i].value;
				update = true;
			}
			if (d[edge[i].b] > d[edge[i].a] + edge[i].value)
			{
				d[edge[i].b] = d[edge[i].a] + edge[i].value;
				update = true;
			}
		}
		if (!update) break;
	}

	cout << d[n] << endl;
}

int main(void)
{
	ll i, a, b, c;

	while (~scanf("%lld %lld", &m, &n))
	{
		for (i = 1; i <= m; i++)
		{
			scanf("%lld %lld %lld", &a, &b, &c);
			edge[i].a = a;
			edge[i].b = b;
			edge[i].value = c;
		}
		solve();
	}
}


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

智能推荐

腾讯副总裁曾宇:谈谈腾讯的技术价值观与技术人才修炼_价值观路落地 腾旭 陆文卓-程序员宅基地

文章浏览阅读2.9k次,点赞3次,收藏4次。作者简介:曾宇先生,腾讯公司副总裁。 2002 年加入腾讯,曾负责腾讯研发线管理,后续担任互动娱乐事业群研发部总经理,负责游戏、互娱相关的技术研发及管理工作,2012 年升任公司 VP,16 年起主要负责移动互联网事业群技术管理工作,继续参与公司级技术管理工作。正文技术人员的核心素养腾讯的职业发展通道大概有 6 级,1 级是初入者,2 级是有经验者,3 级是骨干,4 级是专家,5 级和 6 级是权_价值观路落地 腾旭 陆文卓

html属于页面的底部标签是,HTML5中footer标签的用法你知道吗?,HTML5中的footer标签是什么意思?...-程序员宅基地

文章浏览阅读3.2k次。HTML5中footer标签的用法你知道吗?,HTML5中的footer标签是什么意思?本篇文章就为大家介绍HTML5中footer标签的定义和具体用法,还有footer中的标准属性,还有置于页面最底部的简单实现方法。HTML5中footer标签定义和用法: 标签定义 section 或 document 的页脚。在典型情况下,该元素会包含创作者的姓名、文档的创作日期以及/或者联系信息。在一个文档..._html5底部标签

CentOS7部署l2tp/IPsec服务-程序员宅基地

文章浏览阅读2.3k次。1、安装必要的工具yum install vim net-tools wget unzip -y2. 下载安装脚本wget -O StackScript.zip http://files.cnblogs.com/files/think8848/StackScript.zip3. 解压文件unzip StackScript.zip4. 执行..._stackscript centos

Mac终端好玩的事情俄罗斯方块_mac 如何玩俄罗斯方块-程序员宅基地

文章浏览阅读2.3k次。很有儿时上学时候玩的味道:_mac 如何玩俄罗斯方块

基于HI3559的ISP调试(一)_海思3559 isp文档-程序员宅基地

文章浏览阅读1.9k次。项目需要转到基于HI3559调试自研的摄像头,因为海思自己的PQTools在线调试摄像头的ISP,真香。在进行调试之前,注意自己的几个前提条件:(1)查看板子的SDK版本:cat /proc/umap/vpss为v2.0.1.0那么与之对应的其他版本都应该是针对这个版本,而不是v2.0.2.0。即Hi3559A V100R001C02SPC010文件夹下。(2)安装好MCR编译器,必须要下载MCR 2012a(7.17) 32位版本的。安装后在HiPQtools是可以下拉找到HiPQ ISP_海思3559 isp文档

图的m着色问题(回溯法-满m叉树)_图的m着色问题回溯法-程序员宅基地

文章浏览阅读3.5k次,点赞4次,收藏16次。1.问题描述:给定无向连通图G和m种不同的颜色。用这些颜色为图G的所有顶点着色,每个顶点着一种颜色。每条边的2个顶点颜色不同。称为图的m着色。求有多少种方法为图可m着色。示例:该无向连通图每个顶点有3种着色方式,试求图的m着色方案有几种有6种具体过程在下面2.算法设计:很明显,约束条件为相邻顶点的颜色不同。条件:相邻 & 颜色不同图的临接矩阵为a_图的m着色问题回溯法

随便推点

os练习题2_在unix操作系统中,把输入输出设备看作是-程序员宅基地

文章浏览阅读803次。①对存放在单一存储设备(如磁带)上的顺序文件连续存取速度快②顺序文件存放在多路存储设备(如磁盘)上时,在多道程序的情况下,由于别的用户可能驱使磁头移向其它柱面,会降低连续存取的速度。顺序文件多用于磁带从内到外, 硬件系统,操作系统,支撑软件,应用软件。计算机系统由硬件和软件(系统程序+应用程序)组成。在UNIX操作系统中,把输入/输出设备看作是特殊文件。在UNIX..._在unix操作系统中,把输入输出设备看作是

字节跳动高工面试:mysql查询重复数据sql_bytesql.eq-程序员宅基地

文章浏览阅读118次。正文作为后端开发,日常操作数据库最常用的是写操作和读操作。读操作我们下边会讲,这个分类里我们主要来看看写操作时为什么会导致 SQL 变慢。刷脏页脏页的定义是这样的:内存数据页和磁盘数据页不一致时,那么称这个内存数据页为脏页。那为什么会出现脏页,刷脏页又怎么会导致 SQL 变慢呢?那就需要我们来看看写操作时的流程是什么样的。对于一条写操作的 SQL 来说,执行的过程中涉及到写日志,内存及同步磁盘这几种情况。这里要提到一个日志文件,那就是 redo log,位于存储引擎层,用来存储物理日志。在写操_bytesql.eq

MyBatis批量插入数据_mybaits 插入生成语句多一个括号-程序员宅基地

文章浏览阅读1k次。1.普通for循环插入数据controller层package com.stylefeng.guns.modular.business.controller;import com.etone.common.util.MyJdbcUtil;import com.stylefeng.guns.entity.MerchantConnectData;import com.stylefen..._mybaits 插入生成语句多一个括号

[cx_oralce]加速批量插入dataframe到oracle_cxoracle 插入整个dataframe-程序员宅基地

文章浏览阅读1.9k次。在stack overflow上看到的大牛:from sqlalchemy import types,create_enginedtyp = {c:types.VARCHAR(df[c].str.len().max()) for c in df.columns[df.dtypes == 'object'].tolist()}df.to_sql(..., dtype=d..._cxoracle 插入整个dataframe

【清水值预测】基于 matlab RBF神经网络清水值预测【含Matlab源码 822期】_rbf神经网络matlab代码csdn用水量预测-程序员宅基地

文章浏览阅读814次。RBF神经网络清水值预测完整代码和数据,数据可直接替换,适合小白!可提供运行操作视频!_rbf神经网络matlab代码csdn用水量预测

SpringBoot整合Dubbo:注册失败问题 No Spring Bean annotating Dubbo‘s @Service was found under package_no spring bean annotating dubbo @service-程序员宅基地

文章浏览阅读1.7k次。启动zookeeper,启动provider,启动consumer之后,访问报错。There was an unexpected error (type=Internal Server Error, status=500).No provider available from registry 127.0.0.1:2181 for service com.example.interfaceapi.PeopleService on consumer 172.18.71.53 use dubbo vers_no spring bean annotating dubbo @service

推荐文章

热门文章

相关标签