[文章目录]
Description
Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务，设这些城市分别标记为0到n-1，一共有m种航线，每种航线连接两个城市，并且航线有一定的价格。Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多k种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少？
裸的分层图，用spfa搞定
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int n,m,k,start,fna,ans;
int head[11000],to[101000],nxt[101000],data[101000],cnt;
struct node
{int d,u;};
int f[11000][20];
bool v[11000][20];
void add(int x,int y,int z)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
data[cnt]=z;
}
struct cmp
{
bool operator() (const node x,const node y)
{
return f[x.d][x.u]>f[y.d][y.u];
}
};
priority_queue <node,vector <node> ,cmp > q;
void spfa()
{
memset(f,0x3f,sizeof(f));
f[start][0]=0;
node x;
x.d=start;
x.u=0;
q.push(x);v[start][0]=1;
while(!q.empty())
{
x=q.top();
int use=x.u;
q.pop();v[x.d][x.u]=0;
for(int y,i=head[x.d];i;i=nxt[i])
{
if(f[y=to[i]][use]>f[x.d][use]+data[i])
{
f[y][use]=f[x.d][use]+data[i];
if(!v[y][use])
{
v[y][use]=1;
node tmp;
tmp.d=y,tmp.u=use;
q.push(tmp);
}
}
}
if(use==k) continue;
for(int y,i=head[x.d];i;i=nxt[i])
{
if(f[y=to[i]][use+1]>f[x.d][use])
{
f[y][use+1]=f[x.d][use];
if(!v[y][use+1])
{
v[y][use+1]=1;
node tmp;
tmp.d=y,tmp.u=use+1;
q.push(tmp);
}
}
}
}
}
int read()
{
int sum=0;
char c;
c=getchar();
while(c==' '||c=='\n')
c=getchar();
while(c<='9'&&c>='0')
sum=(sum<<3)+(sum<<1)+(c-'0'),c=getchar();
return sum;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
scanf("%d%d",&start,&fna);
for(int x,y,z,i=1;i<=m;i++)
{
x=read();
y=read();
z=read();
add(x,y,z);
add(y,x,z);
}
spfa();
ans=1<<30;
for(int i=0;i<=k;i++)
ans=min(ans,f[fna][i]);
printf("%d",ans);
return 0;
}头一道写读入优化的题