首页 > 其他分享 >#C. 黑暗城堡

#C. 黑暗城堡

时间:2024-09-28 19:44:58浏览次数:7  
标签:2000005 黑暗 di 城堡 ll lj vv dis

#C. 黑暗城堡

  • 题意

设 D[i] 为第 i 号房间与第 1 号房间的最短路径长度;

S[i] 为实际修建的树形城堡中第 i 号房间与第 1 号房间的路径长度

要求对于所有整数 i ( 1<=i <=N ) ,有 S[i]=D[i] 成立的方案数


  • 分析

跑一遍最短路,再\(N^2\)暴力每两个点之间的边

如果\(dis(1,j)=dis(1,i)+w(i,j)\),j的方案数+1

最后用乘法原理全部相乘即可


  • 细节

勿忘mod


#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,rep[2000005],dis[2000005],vis[2000005],lj[1005][1005];
ll head[2000005],tot;
ll mod=(1<<31)-1;
struct nood{
	ll v;
	ll w;
	ll nxt;
}es[2000005];
void adde(ll u,ll v,ll w){
	es[++tot].v=v,es[tot].w=w,es[tot].nxt=head[u],head[u]=tot;
}
void dij(){
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0;
	priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > >q;
	q.push({0,1});//dis,编号
	while(!q.empty()){
		pair<ll,ll> vv=q.top();
		q.pop();
		ll di=vv.first;
		ll bh=vv.second;
		if(di==dis[bh]){
		//cout<<bh<<"start:"<<endl;
			for(int kk=head[bh];kk;kk=es[kk].nxt){
				ll vvv=es[kk].v;
				//cout<<vvv<<" for "<<dis[vvv]<<endl;
				if(dis[vvv]>es[kk].w+di){
					//cout<<vvv<<":::"<<es[kk].w<<"+"<<di<<endl;
					dis[vvv]=es[kk].w+di;
					q.push(make_pair(dis[vvv],vvv));
				}
			}
		}
	} 
}
int main(){
	cin>>n>>m;
	ll x,y,z;
	memset(lj,0x3f,sizeof(lj));
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		//cout<<x<<" "<<y<<" "<<z<<endl;
		adde(x,y,z);
		adde(y,x,z);
		lj[x][y]=lj[y][x]=min(lj[x][y],z);
	}
	dij();
	ll ans=1;
	for(int i=1;i<=n;i++){ 
		//cout<<"dis i for"<<i<<":"<<dis[i]<<endl;
		ll s=0;
		for(int j=1;j<=n;j++){
			if(dis[i]==dis[j]+lj[i][j]&&i!=j&&dis[i]!=0){
				s++; 
			}
		}
		if(s!=0){
			//cout<<s<<endl;		
			ans=(ans*s)%mod;
			//cout<<ans<<endl;
			ans%=mod;
		}
	}
	cout<<ans;
}

标签:2000005,黑暗,di,城堡,ll,lj,vv,dis
From: https://www.cnblogs.com/Misty-post/p/18438316

相关文章

  • 树上差分+lca 黑暗的锁链
    //**太久不写了,感觉很难受。。。比赛最近打得也不好,课内任务又重,还要忙着做项目。何去何从。今天又写了一题,用了树上差分的知识。下面来整理整理。1.首先让我们学一下lca(最小公共父节点) 我用的是倍增来求的。总共其实就是两步:dfs打ST表预处理每个点的上面节点 lca求两......
  • 黑暗之魂 I&#038;II 合集,豪华中文,重制最终版-灭绝深渊-原罪学者+全DLC+修改器,解压即
    游戏截图《黑暗之魂I&II合集》是一款由FromSoftware开发的经典动作角色扮演游戏合集,囊括了《黑暗之魂》系列的前两部作品:《黑暗之魂:重制版》和《黑暗之魂II:原罪学者》。该合集为玩家提供了进入深邃而神秘的黑暗奇幻世界的机会,体验系列标志性的高难度战斗和复杂的叙事设......
  • 植物在黑暗中的活动
    晚上温度低,降低植物的呼吸作用,会让更多的有机物保存下,导致植物的口感更丰富,比如更甜,更香。随着植物的生长,将植物的一部分填埋起来,会让植物的不见光部分更多的保留有机物,比如章丘大葱。植物在黑暗中进行一系列重要的生理活动,主要包括以下几个方面:呼吸作用:在光照下,植物通过......
  • 黑暗之魂2缺失steam_api.dll该如何处理?全面解读《黑暗之魂2》steam_api.dll丢失及高效
    在游戏的世界中,《黑暗之魂2》凭借其独特的魅力吸引了众多玩家。然而,有时玩家会遭遇steam_api.dll文件丢失的困扰,这无疑给游戏体验带来了极大的阻碍。在这篇文章中,我们将为您进行全面解读。首先深入剖析steam_api.dll文件丢失的原因。可能是由于游戏安装过程中的错误、系统更新......
  • Loj P10064 黑暗城堡 题解 最短路径树记数
    这道题是一道最短路径树问题。首先,什么是最短路径树呢?定义一个图的最短路径树表示一个图上的生成树,且根节点到图上任一点的距离等于原图上两者之间的距离。而不难发现,题目其实是在求图上最短路径树记数。首先,建出最短路径树。枚举每条边,判断边两个端点到根的距离之差是否为......
  • P1504 积木城堡/01背包板子
    代码:#define_CRT_SECURE_NO_WARNINGS#include<iostream>#include<vector>#include<algorithm>#include<math.h>#include<sstream>#include<string>#include<string.h>#include<iomanip>#include<stdlib.h>......
  • 《渣男代码历险记》第三章:天谴之子——光明与黑暗的对决
    “醒醒!醒醒!”“我这是在哪?”二。“你昏睡了34天了。”舅舅。“发生了什么?”舅舅哽咽了,半天说不出话来。“你。。。。。。是天谴之子。”“你为什么这样说?”“你只有放弃人类的未来,才能获得自身的幸福。现在全人类都被代码灭亡了。你答对一个计算机题目,就可以救若干个人类。......
  • 告别复制粘贴的黑暗时代!教你们一个新崛起的API
    在前端开发的世界里,复制粘贴功能就像是那个总是被忽视,却在关键时刻能救你一命的老朋友。我们习惯了用那些古老的魔法咒语(document.execCommand('copy'))来实现这一功能,但时代在进步,技术在更新,是时候告别那些让人头疼的兼容性问题,迎接新时代的剪贴板API了。旧时代的遗物在那个......
  • 黑暗城堡
    acwing链接原本以为是给我所有点到1号点的距离,然后问我有多少棵树满足这个要求。(一个明显是dp的dp吧)其实差不多,但是它已经把所有能选的边给你了。差别就是我枚举的时候多了一个要求。所以这题就是先跑一遍单源最短路,然后把所有点按照dist排序。以为没有负边,所以dist大的点一......
  • 《黑暗欺骗》c++控制台 2D 版!Alpha 0.2.1
    现在只打了设置这些个东西,游戏主体还没打,那才是难点已实现功能游戏未实现设置有音量设置和键盘设置两个功能存档(这好像是最简单的功能吧?)注意事项!!!没错,如你所见,这个游戏我是使用了MCI来播放声音的!因此,你的DEV-C++需要链接到一个库打开工具->编译选项->编译器-......