[USACO09FEB]Revamping Trails G——分层图最短路

用(dijskra)

题面链接

题面

约翰一共有 (N) 个牧场.由 (M) 条布满尘埃的小径连接。小径可以双向通行。每天早上约翰从牧场 (1) 出

发到牧场 (N) 去给奶牛检查身体。

通过每条小径都需要消耗一定的时间。约翰打算升级其中 (K) 条小径，使之成为高速公路。在高速公路上

的通行几乎是瞬间完成的，所以高速公路的通行时间为 (0)。

请帮助约翰决定对哪些小径进行升级，使他每天从 (1) 号牧场到第 (N) 号牧场所花的时间最短。

思路

裸的分层图

正边权的图，记得用(dijskra),记得用(dijskra),卡(spfa)卡到你哭

注意

我们还需要在相邻两层图之间的终点连边

解释见代码

 for(int i=1;i<=k;i++)
 add(n+(i-1)*n,n+i*n,0);//防止毒瘤数据，k 次机会还没用完就到终点了

代码

#include<bits/stdc++.h>
using namespace std;
const int N=6e6;
int ne[N],ver[N],e[N],idx,head[N];
int n,m,k;
void add(int u,int v,int w)
{
    ver[idx]=v;
    ne[idx]=head[u];
    e[idx]=w;
    head[u]=idx;
    idx++;
}
typedef pair<int,int> PII;
long long dist[N];
bool vis[N];
void dij(int s)
{
	memset(dist,0x3f,sizeof(dist));
	dist[s]=0;
	vis[s]=0;
	priority_queue<PII ,vector<PII > ,greater<PII > > q;
	q.push({0,s});
	while(q.size())
	{
		PII  t=q.top();
		q.pop();
		int x=t.second;
		if(vis[x])continue;
		vis[x]=1;
		for(int i=head[x];i!=-1;i=ne[i])
		{
			int j=ver[i];
			if(dist[j]>dist[x]+e[i])
			{
				dist[j]=dist[x]+e[i];
				q.push({dist[j],j});
			}
		}
	}
}

int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
        add(b,a,c);
        for(int j=1;j<=k;j++)
        {
            add(a+(j-1)*n,b+j*n,0);//岔开进行加边，因为我们加了零边之后，我们的程序可定会选择走零边，所以就相当于我们让一条边的权值变成了0
            add(b+(j-1)*n,a+j*n,0);//相同的操作
            add(a+j*n,b+j*n,c);
            add(b+j*n,a+j*n,c);
        }
    }
    for(int i=1;i<=k;i++)
    add(n+(i-1)*n,n+i*n,0);//防止毒瘤数据，k 次机会还没用完就到终点了
    dij(1);
   	cout<<dist[n+n*k]<<endl;
	return 0;
}