P4568 [JLOI2011]飞行路线(分层图最短路)
lzc2001
·
·
个人记录
题目传送门
题目大意
有n(1\leq n\leq 10^4)个顶点，m(1\leq m\leq 5\times10^4)条无向边，边权为wi(1\leq wi\leq 10^3)，最多可以将其中的k(0\leq k\leq 10)条边的边权变为0，求s-t的最短路。
思路
这是一道分层图最短路的模板题，有2种解法。
Solution1
建分层图，顶点i+j\times n表示进行了j次变0操作后到达的i点，如果原图中有边u-v，则在分层图中有边(u+j\times n)-(v+j\times n),权值不变,同时还要连单向边(u+j\times n)->(v+(j+1)\times n)和(v+j\times n)->(u+(j+1)\times n)，边权为0。
**注意数组一定要开够！！！**
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn1 200005
#define maxn2 2100005//数组一定要开够
#define INF 2200000000
template<typename T>void read(T& x){
int f=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){f|=(ch=='-');ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
if(f)x=-x;
}
int head[maxn1],to[maxn2],nxt[maxn2],vis[maxn1],cnt=0;
ll d[maxn1],w[maxn2];
int n,m,k;
struct node{
ll d;
int x;
node(ll d,int x):d(d),x(x){}
bool operator < (const node& a)const{
return d>a.d;
}
};
void add(int u,int v,ll ww){
nxt[++cnt]=head[u];
to[cnt]=v;
w[cnt]=ww;
head[u]=cnt;
}
ll dij(int s,int t){
for(int i=0;i<=(k+1)*n-1;++i)d[i]=INF;
memset(vis,0,sizeof(vis));
priority_queue<node>q;
d[s]=0;
q.push(node(0,s));
while(!q.empty()){
int u=q.top().x;q.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=head[u];i!=-1;i=nxt[i]){
int v=to[i];
if(d[v]>d[u]+w[i]){
d[v]=d[u]+w[i];
q.push(node(d[v],v));
}
}
}
ll ans=INF;
for(int i=0;i<=k;++i)
ans=min(ans,d[t+i*n]);
return ans;
}
int main(){
int s,t;
int u,v,ww;
read(n),read(m),read(k);
read(s),read(t);
for(int i=0;i<=(k+1)*n-1;++i)head[i]=-1;
for(int i=1;i<=m;++i){
read(u),read(v),read(ww);
for(int j=0;j<=k;++j){
add(u+j*n,v+j*n,ww);
add(v+j*n,u+j*n,ww);
if(j!=k){
add(u+j*n,v+(j+1)*n,0);
add(v+j*n,u+(j+1)*n,0);
}
}
}
printf("%lld",dij(s,t));
return 0;
}
```
### Solution2
用$d[sta][v]$表示从$s$到$v$使用了$sta$次变$0$操作后的最短路长度，本质上是DP，具体转移方程看代码。
$ans$即为$d[sta][t](0\leq sta\leq k)$的最小值。
相比于第一种解法,这种解法更快,也更省空间。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn1 10005
#define maxn2 100005
#define INF 0x3f3f3f3f
template<typename T>void read(T& x){
int f=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){f|=(ch=='-');ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
if(f)x=-x;
}
int head[maxn1],to[maxn2],nxt[maxn2],w[maxn2],cnt=0;
int d[11][maxn1],vis[11][maxn1];
int n,m,k;
struct node{
int d,x,sta;
node(int d,int x,int sta):d(d),x(x),sta(sta){}
bool operator < (const node& a)const{
return d>a.d;
}
};
void add(int u,int v,int ww){
nxt[++cnt]=head[u];
to[cnt]=v;
w[cnt]=ww;
head[u]=cnt;
}
int dij(int s,int t){
memset(d,INF,sizeof(d));
memset(vis,0,sizeof(vis));
priority_queue<node>q;
d[0][s]=0;
q.push(node(0,s,0));
while(!q.empty()){
int u=q.top().x,sta=q.top().sta;q.pop();
if(vis[sta][u])continue;
vis[sta][u]=1;
for(int i=head[u];i!=-1;i=nxt[i]){
int v=to[i];
if(d[sta][v]>d[sta][u]+w[i]){
d[sta][v]=d[sta][u]+w[i];
q.push(node(d[sta][v],v,sta));
}
if(sta+1<=k&&d[sta+1][v]>d[sta][u]){//一定要判断sta+1<=k，否则会RE\WA
d[sta+1][v]=d[sta][u];
q.push(node(d[sta+1][v],v,sta+1));
}
}
}
int ans=INF;
for(int i=0;i<=k;++i)
ans=min(ans,d[i][t]);
return ans;
}
int main(){
int s,t;
int u,v,ww;
read(n),read(m),read(k);
read(s),read(t);
memset(head,-1,sizeof(head));
for(int i=1;i<=m;++i){
read(u),read(v),read(ww);
add(u,v,ww);
add(v,u,ww);
}
printf("%d",dij(s,t));
return 0;
}
```