[JLOI2011]飞行路线 (分层图,最短路)

题目链接

Solution

建立 \(k+1\) 层图跑 \(Dijkstra\) 就好了.

Code

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=200008;

int n,m,k,s,t;

struct sj{

	int to;

	int next;

	int w;

}a[maxn*10];

int head[maxn],size;

ll dis[maxn],dist[maxn];

void add(int x,int y,int w)

{

	a[++size].to=y;

	a[size].next=head[x];

	head[x]=size;

	a[size].w=w;

}

int read()

{

	char ch=getchar(); int f=1,w=0;

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch<='9'&&ch>='0'){w=w*10+ch-'0';ch=getchar();}

	return f*w;

}

struct node {

    int u;ll d;

    bool operator <(const node& rhs) const {

        return d>rhs.d;

    }

};

inline void Dijkstra()

{

	memset(dis,127,sizeof(dis));

	dis[s]=0;

	priority_queue<node> q;

	q.push((node){s,0});

	while(!q.empty())

	{

		node xx=q.top(); q.pop();

		int u=xx.u,d=xx.d;

		if(d!=dis[u])continue;

		for(int i=head[u];i;i=a[i].next)

		{

			int tt=a[i].to,w=a[i].w;

			if(dis[u]+w<dis[tt])

			{

				dis[tt]=dis[u]+w;

				q.push((node){tt,dis[tt]});

			}

		}

	}

}

void pre(int x,int y,int w)

{

	for(int i=0;i<=k;i++)

	add(x+n*i,y+n*i,w),

	add(y+n*i,x+n*i,w);

	for(int i=0;i<k;i++)

	add(x+n*i,y+n*i+n,0),

	add(y+n*i,x+n*i+n,0);

}

int main()

{

	n=read(); m=read(); k=read();

	s=read(); t=read();

	for(int i=1;i<=m;i++)

	{

		int x,y,w;

		x=read();

		y=read();

		w=read();

		pre(x,y,w);

	}

	for(int i=0;i<=k;i++)

	add(t+i*n,n*(k+1)+1,0);

	Dijkstra();

	cout<<dis[n*(k+1)+1]<<endl;

}