【分层图最短路】【学习笔记】

【分层图最短路】【学习笔记】

例题1
分析：
设f[i][j]为从1走到i，已指定j条路径边权为0，边权和的最小值，那么有
f[i][j]+w[i,y]——>f[y][j],
f[i][j]——>f[y][j+1]，\((i,y)\in E\)
f[1][0]=0.
则答案为f[n][k]
实际上就是求从(1,0)到(n,k)的最短路，但可以不用真的建出分层图，注意判断不要让j超过k。
因为边权非负，用dij转移即可。

Code

#include
using namespace std;
//#define int long long
inline int read()
{
	int x=0,w=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') {w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*w;
}
inline void write(int x)
{
	if(x<0) putchar('-'),x=~(x-1);
	if(x>9) write(x/10);
	putchar('0'+x%10);
}
const int N=1e4+100;
int n,m,k,d[N][22],vis[N][22];
int hd[N],cnt;
struct node{
	int nxt,to,w;
}e[N*10];
void add(int x,int y,int z)
{
	e[++cnt].nxt=hd[x];
	e[cnt].w=z;
	e[cnt].to=y;
	hd[x]=cnt;
} 
priority_queue > >q;
void dij()
{
	memset(d,0x3f,sizeof d);
	d[1][0]=0;
	q.push(make_pair(0,make_pair(1,0)));
	while(q.size())
	{
		pairx=q.top().second;q.pop();
		int f=x.first,s=x.second;
		if(vis[f][s]) continue;
		vis[f][s]=1;
		for(int i=hd[f];i;i=e[i].nxt)
		{
			int y=e[i].to;
			if(d[y][s]>d[f][s]+e[i].w) d[y][s]=d[f][s]+e[i].w,q.push({-d[y][s],{y,s}});
			if(sd[f][s]) d[y][s+1]=d[f][s],q.push({-d[y][s+1],{y,s+1}});
		}
	}
}
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);
	}
	dij();
	write(d[n][k]);
	return 0;
}

例题2
与上一题类似，用dij求解即可。

Code

#include
using namespace std;
//#define int long long
inline int read()
{
	int x=0,w=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') {w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*w;
}
inline void write(int x)
{
	if(x<0) putchar('-'),x=~(x-1);
	if(x>9) write(x/10);
	putchar('0'+x%10);
}
const int N=55,M=1e3+100;
int hd[N],cnt;
struct node{
	int nxt,to,w;
}e[M<<1];
void add(int x,int y,int z)
{
	e[++cnt].w=z;
	e[cnt].to=y;
	e[cnt].nxt=hd[x];
	hd[x]=cnt;
}
int f[N][N],n,m,k,vis[N][N];
priority_queue > >q;
void dij()
{
	memset(f,0x3f,sizeof f);
	for(int i=0;i<=k;++i) f[1][i]=0,q.push({0,{1,i}});
	while(q.size())
	{
		int x=q.top().second.first,y=q.top().second.second;q.pop();
		if(vis[x][y]) continue;
		vis[x][y]=1;
		if(x==n&&y==k) return; 
		for(int i=hd[x];i;i=e[i].nxt)
		{
			int j=e[i].to;
			if(f[j][y]>f[x][y]+e[i].w)f[j][y]=f[x][y]+e[i].w,q.push({-f[j][y],{j,y}});
			if(yf[x][y]+e[i].w/2) f[j][y+1]=f[x][y]+e[i].w/2,q.push({-f[j][y+1],{j,y+1} });
		}
	}
}
signed 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);
	}
	dij();
	write(f[n][k]);
	return 0;
}

总结：
分层图最短路可以看做一种特殊的dp，列出状态转移方程以后，利用最短路算法来求解即可。
另外，分层图中的边一般不用真的建出来，这样也可以节省空间复杂度。