ZOJ 3794 Greedy Driver spfa

ZOJ 3794 Greedy Driver spfa

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

题意:

给定n个点,m条有向边,邮箱容量。

起点在1,终点在n,開始邮箱满油。

以下m行表示起点终点和这条边的耗油量(就是长度)

再以下给出一个数字m表示有P个加油站,能够免费加满油。

以下一行P个数字表示加油站的点标。

再以下一个整数Q

以下Q行 u v 表示在u点有销售站,能够卖掉邮箱里的随意数量的油,每以单位v元。

问跑到终点能获得最多多少元。

先求个每一个点的最大剩余油量 f[i],

再把边反向,求每一个点距离终点的最短路 dis[i]。

然后枚举一下每一个销售点就可以,( f[i] – dis[i] ) * v。

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<math.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define N 10050
#define M 200010
#define inf 1000000
#define ll long long
struct Edge{
	int from, to, dis, nex;
}edge[M], e[M];
int head[N],edgenum;
void add(int u,int v,int d){
	Edge E={u,v,d,head[u]};
	edge[edgenum] = E;
	head[u] = edgenum++;
}
int H[N], edg;
void add2(int u,int v,int d){
	Edge E={u,v,d,H[u]};
	e[edg] = E;
	H[u] = edg++;
}
int n, m, k;
int F[N], T[N];//F是车站 T是贩卖点
int f[N];//起点到这里最多能剩多少油
bool inq[N];
void spfa(){
	queue<int>q;
	memset(f,-1,sizeof f);
	memset(inq, 0, sizeof inq);
	f[1] = k; q.push(1);
	while(!q.empty()){
		int u = q.front(); q.pop(); inq[u] = 0;
		for(int i = head[u]; ~i; i = edge[i].nex){
			int v = edge[i].to;
			if(f[v]< f[u] - edge[i].dis){
				if(F[v])f[v]=k;
				else
				f[v] = f[u] - edge[i].dis;
				if(!inq[v])inq[v] = 1, q.push(v);
			}
		}
	}
}
int dis[N];//把边反一下跑出距离终点的最短路,也就是从这个点到终点最少要多少油
void bfs(){
	for(int i = 1; i <= n; i++)dis[i] = inf;
	memset(inq, 0, sizeof inq);
	dis[n] = 0;
	queue<int>q; q.push(n);
	while(!q.empty()){
		int u = q.front(); q.pop(); inq[u] = 0;
		for(int i = H[u]; ~i ; i = e[i].nex){
			int v = e[i].to;
			
			if(dis[v]>dis[u]+e[i].dis){
				if(F[v])dis[v] = 0; //由于v是加油站,所以到这点剩下0的油量也没事,自然会补满的
				else
				dis[v] = dis[u]+e[i].dis;
				if(!inq[v])inq[v] = 1, q.push(v);
			}
		}
	}
}
void init(){memset(head, -1, sizeof head);edgenum = 0;memset(H, -1, sizeof H);edg = 0;}
int main(){
	int i,u,v,d;
	while(~scanf("%d %d %d",&n,&m,&k)){
		init();
		memset(F, 0, sizeof F);
		memset(T, 0, sizeof T);
		while(m--){
			scanf("%d %d %d",&u,&v,&d);
			add(u,v,d);
			add2(v,u,d);
		}
		scanf("%d",&m);		while(m--){scanf("%d",&u);F[u]=1;}
		scanf("%d",&m);		while(m--){scanf("%d %d",&u,&v);T[u]=v;}
		spfa();
		if(f[n]==-1){puts("-1");continue;}
		bfs();
		int ans = 0;
		for(int i = 1; i <= n; i++)if(T[i] && f[i]!=-1&&dis[i]<inf)
			ans = max(ans, (f[i] - dis[i])*T[i]);
		cout<<ans<<endl;
	}
	return 0;
}
/*
2 1 1
1 2 2
1
1
0


*/

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118579.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • ghost备份还原详细步骤_ghost一键备份还原

    ghost备份还原详细步骤_ghost一键备份还原注意点1:整个过程中不可动鼠标,使用键盘和触摸板操作。开始备份或还原后中不要动键盘备份从大白菜系统盘等方法进入GHOST依次进入Local→Partition(分区)→ToImage(到镜像文件)选择备份分区所在磁盘选择分区选择储存分区,写文件名字注意点2:移动备份后的文件极易造成文件的损坏,所以这里的位置一定要选好,之后不要移动位置选择压缩率(一般…

  • jdbc的增删改查_使用jdbc完成数据的增删改查

    jdbc的增删改查_使用jdbc完成数据的增删改查JBDC数据的持久化:把数据保存到磁盘上。JDBC是java访问数据库的基石,JDO,Hibernate,Mybatis等都是基于JDBCJDBC是一个独立于特定数据库的管理系统,通用的SQL数据库存取和操作的公共接口配置文件:jdbc.propertiesuser=rootpassword=abc123url=jdbc:mysql://localhost:3306/testdriverClass=com.mysql.jdbc.Driver获取Connectionpublic s

  • FabricJS gotchas/FabricJS陷阱[通俗易懂]

    FabricJS gotchas/FabricJS陷阱[通俗易懂]FabricJSgotchas这个页面包含了第一次接触fabricJS的人打开的最常见问题的列表。这些缺陷的产生,既有解释不清的原因,也有文档不完善的原因。在这里,我们试图解决共同的问题。Objectsarenomoreselectable-setCoords(对象不再是可选择的-setCoords)Fabric包含两组坐标以快速知道物体在画布上的位置。它们链接到两个对象属性:oCoords和aCoords。当用户与对象交互或结束变换(例如拖动)时,fabricJS会自动更新这些坐标。

    2022年10月24日
  • python django环境搭建_python的django框架

    python django环境搭建_python的django框架Django是一个由Python编写的一个开放源代码的Web应用框架。使用Django,只要很少的代码,Python的开发人员就可以轻松地完成一个正式网站所需要的大部分内容,并进一步开发出全功能的Web服务。Python+Django是快速开发、设计、部署网站的最佳组合。Django版本与Python环境的对应表如下,建议对照表来选择Django和Python版本,以免造成不兼容等问题。 Django版本 Python版本 …

  • 为总结经验 为后续工作(关于靠谱的心得体会)

    缘起&amp;amp;amp;amp;amp;amp;nbsp;&amp;amp;amp;amp;amp;amp;nbsp;&amp;amp;amp;amp;amp;amp;nbsp;&amp;amp;amp;amp;amp;amp;nbsp;上一周,电脑突然蓝屏崩溃了,幸亏在保质期内,厂家给免费维修,据说硬盘坏了,因此导致了所有数据丢失,虽然没有太多重要的,内心仍不是个滋味。于是打算将所有的不是特别重要东西能放到云端的都放到云端去。内容(会持续更新)&amp

  • Windows注入与拦截(1) — DLL注入的基本原理「建议收藏」

    Windows注入与拦截(1) — DLL注入的基本原理「建议收藏」一.DLL注入技术的用途从前面的《Windows内存体系》系列文章中我们可以知道,在Windows系统中,每个进程都有自己私有的地址空间。当我们用指针来引用内存的时候,指针的值表示的是进程自己的地址空间的一个虚拟的内存地址。进程不能通过指针来引用其他进程地址空间的内存。因此,如果一个进程有缺陷会导致其引用和覆盖随机地址处的内存,那么这个缺陷的影响就会不会扩散到其他的进程。独立的地址空间有…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号