[BZOJ]2763飞行路线[JLOI2011]

Description

Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务，设这些城市分别标记为0到n-1，一共有m种航线，每种航线连接两个城市，并且航线有一定的价格。Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多k种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少？

Input

数据的第一行有三个整数，n,m,k，分别表示城市数，航线数和免费乘坐次数。

第二行有两个整数，s,t，分别表示他们出行的起点城市编号和终点城市编号。$$ (0 \leq s,t <n )$$

接下来有m行，每行三个整数，a,b,c，表示存在一种航线，能从城市a到达城市b，或从城市b到达城市a，价格为c。

$$(0 \leq a,b <n , a与b不相等 , 0 \leq c \leq 1000)$$

Output

只有一行，包含一个整数，为最少花费。

Sample Input

Sample Output

HINT

对于30%的数据,$$2\leq n \leq 50,1 \leq m \leq 300,k=0$$;

对于50%的数据,$$2 \leq n \leq 600,1 \leq m \leq 6000,0 \leq k \leq 1$$;

对于100%的数据,$$2 \leq n \leq 10000,1 leq m \leq 50000,0 \leq k \leq 10$$.

思路

SPFA/dijstra 分层

分别对用或不用血包进行SPFA

代码

hzwer标准SPFA

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int d[10001][11],head[10001],q[100001][2];
int n,m,k,cnt,st,ed;
bool inq[10001][11];
struct data{int to,next,v;}e[100001];
void ins(int u,int v,int w)
{e[++cnt].to=v;e[cnt].v=w;e[cnt].next=head[u];head[u]=cnt;}
void spfa()
{
    int t=0,w=1;
    memset(d,127/3,sizeof(d));
    q[0][0]=st;q[0][1]=0;
    inq[st][0]=1;d[st][0]=0;
    while(t!=w)
    {
        int now=q[t][0],tmp=q[t++][1];
        if(t==100001)t=0;
        for(int i=head[now];i;i=e[i].next)
        {
            int to=e[i].to;
            if(d[now][tmp]+e[i].v<d[to][tmp])
            {
                d[to][tmp]=d[now][tmp]+e[i].v;
                if(!inq[to][tmp])
                {
                    inq[to][tmp]=1;
                    q[w][0]=to;q[w++][1]=tmp;
                    if(w==100001)w=0;
                }
            }
            if(d[now][tmp]<d[to][tmp+1]&&tmp<k)
            {
                d[to][tmp+1]=d[now][tmp];
                if(!inq[to][tmp+1])
                {
                    inq[to][tmp+1]=1;
                    q[w][0]=to;q[w++][1]=tmp+1;
                    if(w==100001)w=0;
                }
            }
        }
        inq[now][tmp]=0;
    }
    int ans=0x7fffffff;
    for(int i=0;i<=k;i++)
       ans=min(ans,d[ed][i]);
    printf("%d",ans);
}
int main()
{
    scanf("%d%d%d%d%d",&n,&m,&k,&st,&ed);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        ins(u,v,w);ins(v,u,w);
    }
    spfa();
    return 0;
}

SPFA+手写双向队列60分

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

int n,m,K;
int s,t;
int cnt=0;
struct node
{
    int v,nxt,val;
}e[10010];
int heads[10010];
int f[10010][15];//到第i个城市 用了j个血包 损失血量 
bool vis[10010][15];
int q1[10010],q2[10010];

void add_edge(int u,int v,int val)
{
    cnt++;
    e[cnt].val=val;e[cnt].v=v;e[cnt].nxt=heads[u];heads[u]=cnt;
}

void SPFA()
{
    int head,tail;
    memset(f,0x3f,sizeof(f));f[s][0]=0;vis[s][0]=1;
    q1[tail]=s,q2[tail]=0;tail++;
    while(head!=tail)
    {
        int h1=q1[head],h2=q2[head];
        vis[h1][h2]=0;
        head=(head+1)%10010;
        for(int i=heads[h1];i;i=e[i].nxt)
        {
            //UNUSED
            if(f[h1][h2]+e[i].val<=f[e[i].v][h2])
            {
                f[e[i].v][h2]=f[h1][h2]+e[i].val;
                if(!vis[e[i].v][h2])
                {
                    vis[e[i].v][h2]=1;
                    if(f[e[i].v][h2]<=f[q1[head]][q2[head]])
                    {
                        head=(head-1+10010)%10010;
                        q1[head]=e[i].v;
                        q2[head]=h2;
                    }
                    else
                    {
                        q1[tail]=e[i].v;
                        q2[tail]=h2;
                        tail=(tail+1)%10010;
                    }
                }
            }
            //USED
            if(h2<K && f[h1][h2]<=f[e[i].v][h2+1])
            {
                f[e[i].v][h2+1]=f[h1][h2];
                if(!vis[e[i].v][h2+1])
                {
                    vis[e[i].v][h2+1]=1;
                    if(f[e[i].v][h2+1]<=f[q1[head]][q2[head]])
                    {
                        head=(head-1+10010)%10010;
                        q1[head]=e[i].v;
                        q2[head]=h2+1;
                    }
                    else
                    {
                        q1[tail]=e[i].v;
                        q2[tail]=h2+1;
                        tail=(tail+1)%10010;
                    }
                }
            }

        }
    }
}

int main()
{
    cin>>n>>m>>K;
    cin>>s>>t;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add_edge(a,b,c);add_edge(b,a,c);
    }
    SPFA();
    cout<<f[t][K]<<endl;
}

Candy堆神奇优化SPFA

//
//  main.cpp
//  bzoj2763
//
//  Created by Candy on 9/26/16.
//  Copyright © 2016 Candy. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int N=1e4+5,M=5e4+5,K=11;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int n,m,k,s,t,a,b,c;
struct edge{
    int v,w,ne;
}e[M<<1];
int h[N],cnt=0;
inline void ins(int u,int v,int w){
    cnt++;
    e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;
    cnt++;
    e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;
}
struct hn{
    int u,d,f;
    hn(int a=0,int b=0,int c=0):u(a),d(b),f(c){}
    bool operator<(const hn &rhs)const{return d>rhs.d;}
};
int d[N][K],done[N][K];
void bfs(){
    memset(d,127,sizeof(d));
    priority_queue<hn> q;
    q.push(hn(s,0,0));
    d[s][0]=0;
    while(!q.empty()){
        hn x=q.top();q.pop();
        int u=x.u,dis=x.d,f=x.f;
        if(done[u][f]) continue;
        done[u][f]=1;
        if(u==t){printf("%d",dis);return;}
        for(int i=h[u];i;i=e[i].ne){
            int v=e[i].v,w=e[i].w;
            if(f<k&&!done[v][f+1]&&d[v][f+1]>dis){
                d[v][f+1]=dis;
                q.push(hn(v,dis,f+1));
            }
            if(!done[v][f]&&d[v][f]>dis+w){
                d[v][f]=dis+w;
                q.push(hn(v,d[v][f],f));
            }
        }
    }
}
int main(int argc, const char * argv[]) {
    n=read();m=read();k=read();s=read();t=read();
    for(int i=1;i<=m;i++){a=read();b=read();c=read();ins(a,b,c);}
    bfs();
    return 0;
}

[BZOJ]飞行路线