bzoj 3889: [Usaco2015 Jan]Cow Routing SPFA-程序员宅基地

技术标签: BZOJ题解  水题  USACO  ——————图论——————  SPFA  

题目链接


双键值最短路,SPFA


代码:

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>

#define ll long long
#define inf 0X3f3f3f3f3f3f3f3fll

using namespace std;

struct node{
	int to,len1,len2;
};

int s,e,m,n=0;
vector<node>v[3030];
ll dis[3030],num[3030];
bool vis[3030];
queue<int>q;

void link(int x,int y,int z1,int z2){
	node t;
	t.to=y;
	t.len1=z1;
	t.len2=z2;
	v[x].push_back(t);
}

int main(){
	scanf("%d%d%d",&s,&e,&m);
	while(m--){
		int x,y;
		scanf("%d%d",&x,&y);
		vector<int>a;
		for(int i=0; i<y; i++){
			int z;
			scanf("%d",&z);
			n=max(n,z);
			for(int j=0; j<a.size(); j++){
				link(a[j],z,x,a.size()-j);
			}
			a.push_back(z);
		}
	}
	for(int i=1; i<=n; i++){
		dis[i]=inf;
		num[i]=inf;
	}
	q.push(s);
	dis[s]=0;
	num[s]=0;
	vis[s]=true;
	while(!q.empty()){
		int t=q.front();
		q.pop();
		vis[t]=false;
		if(t==e)continue;
		for(int i=0; i<v[t].size(); i++){
			int to=v[t][i].to;
			int len1=v[t][i].len1;
			int len2=v[t][i].len2;
			if(dis[to]>dis[t]+len1){
				dis[to]=dis[t]+len1;
				num[to]=num[t]+len2;
				if(!vis[to])q.push(to),vis[to]=true;
			}
			else if(dis[to]==dis[t]+len1 && num[to]>num[t]+len2){
				num[to]=num[t]+len2;
				if(!vis[to])q.push(to),vis[to]=true;
			}
		}
	}
	if(dis[e]>=inf)printf("-1 -1\n");
	else printf("%lld %lld\n",dis[e],num[e]);
	
	return 0;
}

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

智能推荐

JSON格式转换为Java对象_将json数据转换成java对象-程序员宅基地

文章浏览阅读1.6k次,点赞4次,收藏3次。(一)转换为Java对象代码@Test public void test04() throws IOException { String json ="{\"gender\":\"男\",\"age\":23,\"username\":\"ALworm\"}"; ObjectMapper mapper = new ObjectMapper(); ..._将json数据转换成java对象

c深入剖析跨函数调用指针(多级指针)问题-程序员宅基地

文章浏览阅读2.7k次,点赞2次,收藏5次。在c语言中,如果想要通过函数调用来改变值,有两种方式,第一种是通过指针的传递来改变值(这种可以一次改变多个变量的值),第二种是通过函数的返回值来传递值。第一种,中传递的时候其实只是地址的传递,相对第二种的值传递来说,第一种的效率要高不少,因为第一种传递的是地址,四个字节(部分计算机)大小的地址。特别,是在c中做字符串的处理时,这种第一种情况用的非常的多,我当时也是在做字符串处理的时候遇到这些问题,_跨函数调用

ffmpeg mp4 提取h265命令行_安装FFmpeg多媒体库,以及命令行程序使用介绍-程序员宅基地

文章浏览阅读1k次。FFmpeg是非常流行的多媒体框架,主要用于音视频的解码、编码、转码、混流、过滤、播放等操作。2000年,法国著名的程序员Fabrice Bellard创建FFmpeg项目,前两个字母FF是Fast Forward的意思,同时他也发起MPlayer开源多媒体播放器项目。FFmpeg图标围绕FFmpeg后续将讲解FFmpeg的命令行操作,使用FFmpeg的API编写程序,深入源码进行分析等,本篇介绍..._h265 提取strm

Web网页设计之css_4. css 其他选择器_网页设计选择器类型介绍-程序员宅基地

文章浏览阅读1.1k次。我们在说 css 的核心基础的时候,介绍了三种选择器类型,分别是:class 选择器,id 选择器,标签选择器,但是啊,我们日常用到的肯定不止这些,我们这篇主要来说说一些除此之外的其他选择器,这个我们日后工作会常常用到~一、分组选择器先来说说分组选择器的由来,再说这个东西具体怎么用1. 由来我们知道啊,css 层叠样式由很多,但是在一个网页中,肯定有相同、或者说就是一模一样的样式,但是我们总不能一个一个去复制粘贴一遍,所以,为了我们更好的去定义css,我们需要一个选择器可以支持到我们做到这个_网页设计选择器类型介绍

php中统一编码语句,在PHP中比较字符串之前,使编码统一-程序员宅基地

文章浏览阅读84次。我正在开发一项功能,要求我获取网页的内容,然后检查该页面中是否存在某些文本.这是一个反向链接检查工具.问题是-函数在大多数情况下都能完美运行,但是有时,当链接明显位于该页面时,它会将页面标记为没有链接.我已经将其跟踪到视觉上比较输出中的字符串的程度,并且它们匹配得很好,但是使用==运算符,php告诉我它们不匹配.意识到这可能是某种编码问题,所以我决定看看如果在它们上使用base64_encode(...

Linux学习之路(二)查看系统剩余空间_kali查看剩余空间-程序员宅基地

文章浏览阅读523次。Linux下查看系统剩余空间1.查看系统整体空间剩余情况在命令行中输入“df -h”可以查看系统的分配,已使用和可用情况。如下图:2.查看每个文件夹的占用情况在命令行中输入 “du -sh *”可以查看每个文件夹的大小。此举可以快速定位大文件所存在的位置。..._kali查看剩余空间

随便推点

WEB UI基础八:链接跳转到标准的工单界面-程序员宅基地

文章浏览阅读151次。接以前做的例子,用组件做了个搜索界面,明细里添加了object_id的链接: method GET_P_OBJECT_ID."#EC NEEDED** generated by search page wizardif me->running_in_f4_popup( ) = abap_false. case iv_property. when if..._派工单显示页面web端ui

饿了么自动登录解决方案(手机短信登录)_饿了么风神登录-程序员宅基地

文章浏览阅读1.5w次。登录流程:1.注册易码平台,通过易码平台获取 随机的手机号码2.选择短信项目:饿了么,点击获取手机号3.将平台中提供的手机号填入饿了么登录页饿了么登录网址:https://h5.ele.me/login/#redirect=https%3A%2F%2Fh5.ele.me%2Fprofile%2F%23come_from%3Dlogout可能需要点击滑块4.点击验..._饿了么风神登录

matlab filter rayleighchan,关于Matlab中rayleighchan这个函数的使用-程序员宅基地

文章浏览阅读890次。关于Matlab中rayleighchan这个函数的使用12-16各位大哥:关于Matlab中,现在有个rayleighchan这样的函数,它能产生瑞利衰落的信道,但是,其中的有个参数不是很理解,Help里面也没有讲清楚。它其中有个参数叫做:AvgPathGaindB-----average path gains;另外还有一个只读的参数是:PathGains。现在搞不清楚这两个参数之间是什么关系,..._matlab2020 无法调用rayleighchan

ABAP 创建设备BAPI BAPI_EQUI_CREATE-程序员宅基地

文章浏览阅读996次。DATA: EXT_NUMBER TYPE BAPI_ITOB_PARMS-EQUIPMENT. DATA: DATA_GENERAL TYPE BAPI_ITOB. DATA: DATA_GENERAL_EXP TYPE BAPI_ITOB. DATA: DATA_SPECIFIC TYPE BAPI_ITOB_EQ_ONLY. DATA: DATA_INSTALL TYPE BAPI_ITOB_EQ_INSTALL. DATA: RETURN TYPE B._bapi_equi_create

1042 字符统计-程序员宅基地

文章浏览阅读67次。请编写程序,找出一段给定文字中出现最频繁的那个英文字母。输入格式:输入在一行中给出一个长度不超过 1000 的字符串。字符串由 ASCII 码表中任意可见字符及空格组成,至少包含 1 个英文字母,以回车结束(回车不算在内)。输出格式:在一行中输出出现频率最高的那个英文字母及其出现次数,其间以空格分隔。如果有并列,则输出按字母序最小的那个字母。统计时不区分大小写,输出小写字母。输入样例:This is a simple TEST. There ARE numbers and oth

零知识证明应用到区块链中的技术挑战-程序员宅基地

文章浏览阅读1.3k次。零知识证明应用到区块链中的技术挑战李康1,2, 孙毅1,2, 张珺3, 李军4, 周继华5, 李忠诚11. 中国科学院计算技术研究所,北京 100190 2. 中国科学院..._零知识证明技术的国内外研究现状