bzoj 1579: [Usaco2009 Feb]Revamping Trails 道路升级【分层图+spfa】
2024-08-30 21:09:39
至死不用dijskstra系列2333,洛谷上T了一个点,开了O2才过
基本想法是建立分层图,就是建k+1层原图,然后相邻两层之间把原图的边在上一层的起点与下一层的终点连起来,边权为0,表示免了这条边的边权,然后答案就是第0层的s到k层的t的最短路,因为0权边总是从上一层连到下一层,所以到达k层就表示走了k条0权边
这样的点数是nk的,不管是dijskstra还是spfa都跑不过
然后仔细观察这张图的特性,发现不同层之间的更新只有上一层通过0权边更新下一层,所以考虑单层更新,每一层都做一次spfa,然后跨层的时候用上一层跑过的最短路和0权边更新下一层
然后给spfa加一个SLF优化即可
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<ctime>
using namespace std;
const int N=50005,inf=1e9;
int n,m,k,h[N],cnt,dis[N],d[N];
bool v[N];
deque<int>q;
struct qwe
{
int ne,no,to,va;
}e[N<<2];
int read()
{
int r=0,f=1;
char p=getchar();
while(p>'9'||p<'0')
{
if(p=='-')
f=-1;
p=getchar();
}
while(p>='0'&&p<='9')
{
r=r*10+p-48;
p=getchar();
}
return r*f;
}
inline void add(int u,int v,int w)
{
cnt++;
e[cnt].ne=h[u];
e[cnt].no=u;
e[cnt].to=v;
e[cnt].va=w;
h[u]=cnt;
}
void spfa()
{
while(!q.empty())
{
int u=q.front();
q.pop_front();
v[u]=0;
for(int i=h[u];i;i=e[i].ne)
if(dis[e[i].to]>dis[u]+e[i].va)
{
dis[e[i].to]=dis[u]+e[i].va;
if(!v[e[i].to])
{
v[e[i].to]=1;
if(!q.empty()&&dis[q.front()]>dis[e[i].to])
q.push_front(e[i].to);
else
q.push_back(e[i].to);
}
}
}
}
int main()
{
n=read(),m=read(),k=read();
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),z=read();
add(x,y,z),add(y,x,z);
// for(int j=0;j<=k;j++)
// add(x+j*n,y+j*n,z),add(y+j*n,x+j*n,z);
// for(int j=1;j<=k;j++)
// add(x+(j-1)*n,y+j*n,0),add(y+(j-1)*n,x+j*n,0);
}
for(int i=1;i<=n;i++)
dis[i]=inf;
// clock_t st,ed;
// st=clock();
v[1]=1,dis[1]=0,q.push_back(1);
spfa();
for(int con=1;con<=k;con++)
{
for(int i=1;i<=n;i++)
d[i]=inf;
v[1]=1,dis[1]=0,q.push_back(1);
for(int i=1;i<=cnt;i++)
if(d[e[i].to]>dis[e[i].no])
{
d[e[i].to]=dis[e[i].no];
if(!v[e[i].to])
{
v[e[i].to]=1;
if(!q.empty()&&d[q.front()]>d[e[i].to])
q.push_front(e[i].to);
else
q.push_back(e[i].to);
}
}
for(int i=1;i<=n;i++)
dis[i]=d[i];
spfa();
}
// ed=clock();
// cerr<<st<<" "<<ed<<" "<<ed-st<<endl;
printf("%d\n",dis[n]);
return 0;
}
最新文章
- 常用HTML标签元素结合及简介
- 远程debug hadoop
- Android SDK 国内镜像及配置方法
- 解决 Ubuntu 无法调节屏幕亮度的问题(转)
- BFS(判断状态) HDOJ 3533 Escape
- Repeater控件 ---表格展示数据
- IOS 开发环境,证书和授权文件等详解
- Photoshop操作指南
- POJ2676Sudoku(类似于八皇后)
- epoll和poll效率差异
- Cocos2d-x中触摸事件
- 如何升级cordova插件
- 备忘--简单比较SPSS、RapidMiner、KNIME以及Kettle四款数据分析工具
- Sersync同步过滤.svn文件夹
- 不错的 HttpHelper类 c#
- QT server服务端如何判断客户端断开连接
- ##4.Glance 镜像服务-- openstack pike
- springboot 如何操作redis
- [React] 16 - Topic: Mixins &; Higher-Order Components
- Javascript 思维导图 绘制基础内容(值得一看)
热门文章
- add favorite &; 收藏夹
- HDU 4948 (傻比图论)
- [ C语言版 ] 数独计算器 [ 搜索剪枝法 ]
- HDU——1068 Girls and Boys
- Java中如何获取spring中配置的properties文件内容
- 创建Filter步骤
- 1.spring boot要求最低jdk1.8,平安默认1.6问题,-》安装JDK1.8 2.maven 3.3.3要求最低jdk1.7->;安装jdk 1.8
- 物理内存、虚拟内存、buffers、cached、共享内存、swap
- [React] Spread Component Props in JSX with React
- ShadowDOM