首页 > 其他分享 >断网测试2-香甜的黄油

断网测试2-香甜的黄油

时间:2024-01-27 09:04:27浏览次数:27  
标签:le int 牧场 vis 断网 香甜 黄油 奶牛 dis

洛谷P1825

题目描述

Farmer John 发现了做出全威斯康辛州最甜的黄油的方法:糖。

把糖放在一片牧场上,他知道 NNN 只奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。当然,他将付出额外的费用在奶牛上。

Farmer John 很狡猾。像以前的 Pavlov,他知道他可以训练这些奶牛,让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声,以至他可以在晚上挤奶。

Farmer John 知道每只奶牛都在各自喜欢的牧场(一个牧场不一定只有一头牛)。给出各头牛在的牧场和牧场间的路线,找出使所有牛到达的路程和最短的牧场(他将把糖放在那)。

输入格式

第一行包含三个整数 N,P,CN,P,CN,P,C,分别表示奶牛数、牧场数和牧场间道路数。

第二行到第 N+1N+1N+1 行,每行一个整数,其中第 iii 行的整数表示第 i−1i-1i−1 头奶牛所在的牧场号。

第 N+2N+2N+2 行到第 N+C+1N+C+1N+C+1 行,每行包含三个整数 A,B,DA,B,DA,B,D,表示牧场号为 AAA 和 BBB 的两个牧场之间有一条长度为 DDD 的双向道路相连。

输出格式

输出一行一个整数,表示奶牛必须行走的最小的距离和。

输入输出样例

输入 #1
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
输出 #1
8

说明/提示

数据范围

对于所有数据,1≤N≤5001 \le N \le 5001≤N≤500,2≤P≤8002 \le P \le 8002≤P≤800,1≤A,B≤P1 \le A,B \le P1≤A,B≤P,1≤C≤14501 \le C \le 14501≤C≤1450,1≤D≤2551 \le D \le 2551≤D≤255。


样例解释

作图如下:

          P2  
P1 @--1--@ C1
         |
         | 
       5  7  3
         |   
         |     C3
       C2 @--5--@
          P3    P4

把糖放在4号牧场最优。

 

每个点都跑一下dijk即可,但是要堆优化,不然会爆炸

#include <bits/stdc++.h>
using namespace std;

const int N=1005;
struct edge
{
	int v, w;
	bool operator <(const edge &A) const
	{
		return w>A.w;
	}
};
vector<edge> a[N];
int n, p, c, cow[N], u1, v1, w1;
int dis[N], vis[N], sum=0, ans=INT_MAX, flag=0;
priority_queue<edge> q;
void dij(int s)
{
	memset(dis, 63, sizeof dis);
	memset(vis, 0, sizeof vis);
	dis[s]=0, q.push({s, 0});
	
	while (!q.empty())
	{
		int u=q.top().v;
		q.pop();
		
		if (vis[u]) continue;
		vis[u]=1;
		
		for (int i=0; i<a[u].size(); i++)
		{
			int v=a[u][i].v, w=a[u][i].w;
			if (!vis[v] && dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push({v, dis[v]});
			}
		}
	}
}
int main()
{
	scanf("%d%d%d", &n, &p, &c);
	for (int i=1; i<=n; i++) scanf("%d", &cow[i]);
	for (int i=1; i<=c; i++)
	{
		scanf("%d%d%d", &u1, &v1, &w1);
		a[u1].push_back({v1, w1});
		a[v1].push_back({u1, w1});
	}
	
	for (int i=1; i<=p; i++)
	{
		sum=0, flag=0;
		dij(i);
		for (int j=1; j<=n; j++)
		{
			if (dis[cow[j]]==dis[0]) 
			{
				flag=1;
				break;
			}
			sum+=dis[cow[j]];
		}
			
		if (flag==0) ans=min(ans, sum);
	}
	
	printf("%d", ans);
	return 0;
}
/*
2 3 3
1
2
1 2 2
2 3 1
3 1 2
*/

 

标签:le,int,牧场,vis,断网,香甜,黄油,奶牛,dis
From: https://www.cnblogs.com/didiao233/p/17991056

相关文章

  • Android Webview判断网页加载完毕
    原文:AndroidWebview判断网页加载完毕-Stars-One的杂货小窝书接上文,在AndroidWebView获取html源码-Stars-One的杂货小窝此文讲到没有一个可以判断网页加载完毕的方法最近发现确实是有个解决方案,就是设置webViewClient里的onPageFinished方法判断当前webview进度,如下......
  • 解决无线频繁断网,这个办法值得收藏!
    你们好,我的网工朋友。在如今互联网普及率非常高的环境下,我们的日常生活和工作都与网络紧密相连。在追求较高网速的同时,稳定的网络传输质量越来越受到关注。无线网络是现在办公中最常见的弱电网络系统,也是现代生活中最不可缺少的,没有网络,意味着你无法正常开展工作。而在这个过程中一......
  • 小技巧-- 断网恢复(未识别网络-无internet访问权限)
    配置host(解决延迟高问题) 安装java,配置环境变量,直接系统path中bin地址就行,不行就往上面移动 win开机启动Win+R打开运行,输入:shell:startupcalc  打开计算器powercfg/batteryreport 查看电池健康程度 netstat-anotasklist 列出进程 |findstr查询端口......
  • 断网或者杀死进程后,退出房间的最长时间
    RTCSDK5.1.13版本之前:一端杀进程,或是断网,server端会在60s后触发超时逻辑,另一端会收到对端离线的消息。不立刻发送通知是因为断网情况,server要兼容断线重连逻辑,需要对客户端的断网有一个容忍时长(目前是60s),也不会立即发送断线的通知。RTCSDK5.1.13版本及之后:可以提工单......
  • Win11系统安装的断网操作
    Win11系统安装的断网操作1.注意事项   重装系统时可能有些驱动不会自动安装,最好在安装前先提前下载网卡驱动,安装完成后无网络连接时运行驱动,连网后再进行后续操作,不提前准备网卡驱动,安装后没网又没其他设备下载驱动的话就搞笑了(……)。驱动推荐电脑品牌官网下载对应型号驱......
  • AcWing 1127. 香甜的黄油 (dij板子不能背太死, 需要知道含义灵活变通
    package算法提高课;importjava.util.Arrays;importjava.util.PriorityQueue;importjava.util.Scanner;publicclassacw1127{staticintn,p,c;staticint[]id;staticint[]h,e,ne,w;staticboolean[]st;staticint[]d;static......
  • 【Windows】ARP断网攻击及防御
    title:ARP断网攻击及防御date:2022-10-0216:06:44tags:-windowscategories:-windows攻击PC1的IP地址10.9.136.222PC2的IP地址10.9.136.55在局域网里通信需要有IP地址和MAC地址两台电脑PC1和PC2要想相互通信,PC1在连接PC2的时候,PC1会先查看自己的ARP缓存表(命......
  • 装个绿色Xshell,无需注册机,或者需要断网等各种骚操作
    找个能用的真不容易啊。官方免费版,无需下载注册机,或者需要断网等各种骚操作,安装完成后即可使用,非常方便。前言Xshell是一个强大的安全终端模拟软件,它支持SSH1,SSH2,以及MicrosoftWindows平台的TELNET协议。Xshell通过互联网到远程主机的安全连接以及它创新性的设计和特......
  • 常见诊断网络连接是否正确的命令
    背景经常我们需要确认我们使用的主机与目标主机是否连通,若不连通的话,其中在哪里断开测试是否连通:pingip,可选参数-n(定义发送数据包的个数),-t(不间断向目标地址发送数据包,直到我们强迫其停止),-l(设置数据包的大小,一般默认32字节)测试连通路径上有哪些ip:windows使用命令tracert......
  • Windows系统 C/C++程序编译后首次执行时间很长 断网则正常执行 的解决方法
    Windows系统C/C++程序编译后首次执行时间很长断网则正常执行的解决方法问题描述运行环境:Win10、Win11或其他Win环境。在各类IDE(包括但不限于VC6/VisualStuido等)编译任意C/C++源码(无论该程序有多简单),首次运行时间异常地长,即在黑窗口无任何输出。等待一段时间后有程序正......