BZOJ 2763 分层图最短路
2024-08-25 16:46:01
突然发现我不会分层图最短路,写一发。 就是同层中用双向边相连,用单向边连下一层
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <queue>
#include <vector>
#define pa pair<int,int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int Maxm=;
const int Maxn=;
const int Inf=0x3f3f3f3f;
priority_queue<pa,vector<pa>,greater<pa> > Q;
int head[Maxn],dis[Maxn],n,m,k,S,T,u,v,w,cnt;
struct Edge{int to,next,w;}edge[Maxm];
inline void Add(int u,int v,int w)
{edge[cnt].to=v;edge[cnt].next=head[u];edge[cnt].w=w;head[u]=cnt++;}
inline void ADD(int u,int v,int w) {Add(u,v,w),Add(v,u,w);}
inline int Get(int u,int Dep) {return u+(Dep-)*n;} void Dij()
{
Q.push(mp(,Get(S,)));
for (int i=;i<=Get(n,k);i++) dis[i]=Inf;
dis[Get(S,)]=;
while (!Q.empty())
{
int u=Q.top().se; Q.pop();
for (int i=head[u];i!=-;i=edge[i].next)
if (dis[u]+edge[i].w<dis[edge[i].to])
{
dis[edge[i].to]=dis[u]+edge[i].w;
Q.push(mp(dis[edge[i].to],edge[i].to));
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k); k++;
scanf("%d%d",&S,&T); S++,T++;
memset(head,-,sizeof(head));
for (int i=;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w); u++,v++;
for (int j=;j<=k;j++) ADD(Get(u,j),Get(v,j),w);
for (int j=;j<k;j++)
Add(Get(u,j),Get(v,j+),),
Add(Get(v,j),Get(u,j+),);
}
Dij();
printf("%d\n",dis[Get(T,k)]);
return ;
}
C++
最新文章
- 跨域无法获取自定义header的问题
- Objective-C中的Strong、Copy与MutableCopy
- 前端性能优化----yahoo前端性能团队总结的35条黄金定律
- mydetails-yii1
- Android实现网络访问
- PE文件结构详解(三)PE导出表
- Gdb 常用命令
- Probably at least one of the constraints in the following list is one you don&#39;t want.
- scala中的implict
- Android 5.0自定义动画
- .NET Framework不同组件区别及安装注意事项
- 【转】FLEX中SharedObject介绍及应用
- python csv例子
- Error in .Call.graphics(C_palette2, .Call(C_palette2, NULL)) : invalid graphics state
- 01-初识MySQL数据库
- Python和C++的混合编程(使用Boost编写Python的扩展包)
- leetcode — surrounded-regions
- Eonasdan bootstrap datetimepicker 使用记录
- SpringBoot yml properties文件
- Linux下tar.gz 安装