首页 > 其他分享 >分层图

分层图

时间:2024-10-06 08:49:42浏览次数:7  
标签:int Nd back 分层 push first dis

P4568 分层图板子题(卡SPFA)

include<bits/stdc++.h>

define ll long long

using namespace std;
const int N=1e5+10;
int n,m,k,s,t;
ll vis[N<<4],dis[N<<4];
ll ans=INT_MAX;
vector<pair<int,int> > g[N<<4];
void dijkstra(int s)
{
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
q.push({0,s});
dis[s]=0;
while(!q.empty())
{
int u=q.top().second;q.pop();
if(vis[u]) continue ;
vis[u]=1;
for(auto v:g[u])
{
if(dis[v.first]>dis[u]+v.second)
{
dis[v.first]=dis[u]+v.second;
q.push({dis[v.first],v.first});
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
memset(dis,0x7f,sizeof(dis));
// freopen("xxx.in","r",stdin);
// freopen("xxx.out","w",stdout);
cin>>n>>m>>k>>s>>t;
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
for(int d=0;d<=k;d++)
{
g[Nd+a].push_back({Nd+b,c});
g[Nd+b].push_back({Nd+a,c});
if(d<k) g[Nd+a].push_back({N(d+1)+b,0});
if(d<k) g[Nd+b].push_back({N(d+1)+a,0});
}
}
dijkstra(s);
for(int d=0;d<=k;d++)
{
// cout<<dis[Nd+t]<<endl;
ans=min(ans,dis[N
d+t]);
}
cout<<ans<<endl;
return 0;
}

标签:int,Nd,back,分层,push,first,dis
From: https://www.cnblogs.com/After17/p/18448839

相关文章

  • 分层图
    分层图前言在一次模拟赛中,我遇到了[USACO15JAN]GrassCownoisseurG这道题,当时不知如何下手,和边上的同学偷偷讨论,听别人说是分层图,建两份图然后连一层反向边即可,当时对这个图论建模大为惊叹(不亚于我在学网络流时学到拆点拆边),故专门写一篇博客记录之。算法思想分层图是图论......
  • Codeforces2014E Rendez-vous de Marian et Robin(分层图最短路)
    题意给定一个无向图,含有\(n\)个点和\(m\)条边。题解点击查看代码#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;constexpri64inf=1e18;voidsolve(){intn,m,h;cin>>n>>m>>h;vector<vector<......
  • 基于多时间尺度的电动汽车光伏充电站联合分层优化调度(Matlab代码实现)
        ......
  • 经典强化学习算法:分层强化学习算法—options算法2(理解篇)
    论文地址:https://people.cs.umass.edu/~barto/courses/cs687/Sutton-Precup-Singh-AIJ99.pdf例子:这是一个寻路问题,该问题使用强化学习算法解决,准确的来说是使用“表格表示的强化学习算法中的规划算法”来进行解决的;之所以没有说是使用规划算法来说是因为这里使用了学习型......
  • 甄选范文“论企业应用系统的分层架构风格”,软考高级论文,系统架构设计师论文
    论文真题软件架构用来处理软件高层次结构的设计和实施,它以精心选择的形式将若干结构元素进行装配,从而满足系统的主要功能和性能需求。软件架构设计的首要问题是如何表示软件架构,即如何对软件架构建模。根据建模的侧重点不同,可以将软件架构模型分为结构模型、框架模型、动......
  • 经典强化学习算法:分层强化学习算法 —— options算法
    论文地址:https://people.cs.umass.edu/~barto/courses/cs687/Sutton-Precup-Singh-AIJ99.pdf分层强化学习算法options的原论文中的定义:......
  • 基于 Flask 和 Vue 的 MVC 分层结构详解
    在现代web应用开发中,MVC(Model-View-Controller)架构是一种常用的设计模式。它将应用程序分为三部分:模型(Model)、视图(View)和控制器(Controller),以实现清晰的职责分离和代码的可维护性。今天,我们将详细解释如何在Flask和Vue的组合中实现这一架构。一、什么是MVC分层结构Model......
  • 图书分享:《分层强化学习理论与方法》
    地址:https://github.com/devilmaycry812839668/cnblogs-github-sync/blob/main/shareFiles/(已上传百度云盘备份)分层强化学习理论与方法.pdf......
  • 分层图
    分层图引入我们发现,在某些最短路问题中,并不只有一种性质的边,或者说允许改变一些边权。为了处理这样的问题,分层图建模思想应运而生。构建对于这样的问题,我们考虑根据边的不同性质分别建图,在图的内部则是一些普通边,在图与图之间连上那些“特殊的性质边”,换句话说,就是将决策......
  • 【VMware ESXi】如何查看启用内存分层功能的 ESXi 主机使用了多少 NVMe 内存。
    VMwarevSphere8U3中作为技术预览所引入的功能“内存分层(MemoryTiering)”,相信大家已经在自己的测试或实验环境中应用并验证了,如果你还不知道,请跳转到这篇(把硬盘当内存用?VMware内存分层(MemoryTiering),你值得拥有!)文章了解相关介绍以及如何启用它。需要注意的是,目前在启用内存......