[BZOJ2763] [JLOI2011] 飞行路线

题目链接

BZOJ.

洛谷.

Solution

这玩意叫分层图最短路吗?...

一个点拆成(k)个，点(p(x,i))表示到点(x)，用了(i)次免费机会。

那么一条有向边可以拆成(2k)条边：

• 可以选择不用免费机会，那么对于每个(i)，连边(p(u,i) o p(v,i))，边权为(w)。
• 否则对于每个(i)，连边(p(u,i) o p(v,i+1))，边权为(0)。

然后普通的跑最短路就行了。

#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}

#define lf double
#define ll long long 

const int maxn = 2e6+10;
const int inf = 1e9;
const lf eps = 1e-8;

int n,m,k,head[maxn],tot,s,t,dis[maxn];
struct edge{int to,nxt,w;}e[maxn<<1];

inline int p(int x,int y) {return y*n+x;}

void ins(int u,int v,int w) {e[++tot]=(edge){v,head[u],w},head[u]=tot;}

#define fr first
#define sc second
#define mp make_pair

void dijkstra() {
	priority_queue<pair<int,int > > q;
	memset(dis,63,sizeof dis);
	q.push(mp(dis[s]=0,s));
	while(!q.empty()) {
		int now=q.top().sc,d=-q.top().fr;q.pop();
		if(dis[now]<d) continue;
		for(int i=head[now];i;i=e[i].nxt) 
			if(dis[e[i].to]>dis[now]+e[i].w) {
				dis[e[i].to]=dis[now]+e[i].w;
				q.push(mp(-dis[e[i].to],e[i].to));
			}
	}
}

int main() {
	read(n),read(m),read(k),read(s),read(t),s++,t++;
	for(int w=1,x,y,z;w<=m;w++) {
		read(x),read(y),read(z);x++,y++;
		for(int i=0;i<=k;i++) ins(p(x,i),p(y,i),z);
		for(int i=0;i<k;i++) ins(p(x,i),p(y,i+1),0);
		swap(x,y);
		for(int i=0;i<=k;i++) ins(p(x,i),p(y,i),z);
		for(int i=0;i<k;i++) ins(p(x,i),p(y,i+1),0);
	}
	for(int i=0;i<k;i++) ins(p(t,i),p(t,k),0);  //为了防止坑爹数据加上这句话
	dijkstra();
	write(dis[p(t,k)]);
	return 0;
}