浅谈分层图与最短路

Luogu P4568 飞行路线

众所周知，对于经典的最短路问题，我们可以使用各类算法来解决。

但是对于这道题，我们可以选取某些边，改变它的权值。

显而易见的一点就是直接套用SPFA或者Dijkstra并不能解决这个问题。

这时候我们引入一个叫做分层图的东西。

把每一个点复制\(k\)次，形成\(k\)层的图。我们认为当一个点从第\(i\)层到达第\(i+1\)层时就相当于使用了一次更改权值的机会。

那么对于这道题，我们只要对应地建图即可，每一层内正常连边，下层向上层的边权值为\(0\)，上层不能抵达下层。最后跑一次最短路即可。

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=5e7+5,maxm=5e7+5;
struct EDGE
{
    int to,next,val;
}edge[maxm];
int n,m,k,cost[maxn],cnt,head[maxn],s,t,a,b,c;
struct DATA
{
	int id,val;
	bool operator <(const DATA &x) const
	{
		return val>x.val;
	}
};
priority_queue<DATA> que;
bool vis[maxn];
void add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    edge[cnt].val=w;
    head[u]=cnt;
}
void dijkstra()
{
	for (int i=0;i<=n*(k+1);i++) cost[i]=0x3f3f3f3f;
	cost[s]=0;
	DATA sta;sta.id=s;sta.val=0;
	que.push(sta);
    while (!que.empty())
	{
		DATA mini=que.top();
		que.pop();
		if (vis[mini.id]) continue;
		if (mini.val>cost[mini.id]) continue;
		vis[mini.id]=true;
		for (int j=head[mini.id];j;j=edge[j].next)
		{
			int v=edge[j].to;
			if (cost[mini.id]+edge[j].val<cost[v]) 
			{
				cost[v]=cost[mini.id]+edge[j].val;
				DATA tmp;tmp.id=v;tmp.val=cost[v];
				que.push(tmp);
			}
		}
	}
}//heap+dijkstra
int main()
{
    scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        for (int j=0;j<=k;j++)
		{
			add(a+n*j,b+n*j,c);
			add(b+n*j,a+n*j,c);
			if (j==k) break;
			add(a+n*j,b+n*(j+1),0);
			add(b+n*j,a+n*(j+1),0);
            //建图
		}
    }
    dijkstra();
    int ans=0x3f3f3f3f;
    for (int i=0;i<=k;i++)
    	ans=min(ans,cost[t+i*n]);
    printf("%d",ans);
    return 0;
}

例题：

Luogu P1948 Telephone Lines S

Luogu P1073 最优贸易

最优贸易的解法：可以把点复制三份，从第一层到第二层代表买入，从第二层到第三层代表卖出即可。

#include<cstdio>
#include<queue>
using namespace std;
const int maxn=1e5+5,maxm=5e5+5;
struct EDGE
{
	int to,next,val;
}edge[maxm*4];
queue<int> que;
int n,m,cost[3*maxn],head[3*maxn],val,x,y,z,cnt;
bool vis[3*maxn];
void add(int u,int v,int w)
{
	edge[++cnt].to=v;
	edge[cnt].next=head[u];
	edge[cnt].val=w;
	head[u]=cnt;
}
void SPFA()
{
	for (int i=1;i<=3*n;i++) cost[i]=0x3f3f3f3f;
	cost[1]=0;vis[1]=true;que.push(1);
	while (!que.empty())
	{
		int u=que.front();
		que.pop();vis[u]=false;
		for (int i=head[u];i;i=edge[i].next)
		{
			int v=edge[i].to;
			if (cost[v]>cost[u]+edge[i].val)
			{
				cost[v]=cost[u]+edge[i].val;
				if (!vis[v])
				{
					vis[v]=true;
					que.push(v);
				}
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&val);
		add(i,i+n,val);
		add(i+n,i+2*n,-val);
	}
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		z--;
		add(x,y,0);
		add(x+n,y+n,0);
		add(x+2*n,y+2*n,0);
		if (z)
		{
			add(y,x,0);
			add(y+n,x+n,0);
			add(y+2*n,x+2*n,0);
		}
	}
	SPFA();
	if (cost[3*n]<0) printf("%d",-cost[3*n]);
	else printf("0");
	return 0;
}

浅谈分层图与最短路

原文：https://www.cnblogs.com/notscience/p/12975290.html