P4568 [JLOI2011]飞行路线

分层图模板题，相似的题还有P4822 [BJWC2012]冻结，
P2939 [USACO09FEB]改造路Revamping Trails,其实做惯了也就不难了。。

为什么有这篇题解？

  • 感觉写的比较简洁清晰

  • 线段树优化最短路

一、堆优化dijkstra

652ms / 25.58MB / 1.31KB C++

#include
#include
#include
using namespace std;
const int MAXN=110005,MAXM=2500001;
struct edge {
    int to,dis,next;
} e[MAXM];
int n,m,k,s,t,head[MAXN],dis[MAXN],cnt;
bool vis[MAXN];
struct node {
    int dis,pos;
    bool operator <(const node &x)const {
        return x.dis<dis;
    }
};
priority_queue q;
inline void add_edge(int u,int v,int d) {
    e[++cnt].dis=d;
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
inline void dijkstra() {
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    q.push((node) {
        0,s
    });
    while(!q.empty()) {
        node tmp=q.top();
        q.pop();
        int x=tmp.pos,d=tmp.dis;
        if (vis[x]) continue;
        vis[x]=1;
        for (int i=head[x]; i; i=e[i].next) {
            int y=e[i].to;
            if (dis[y]>dis[x]+e[i].dis) {
                dis[y]=dis[x]+e[i].dis;
                if (!vis[y])
                    q.push((node) {
                    dis[y],y
                });
            }
        }
    }
}
int main() {
    scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
    for (register int i=0; i<m; i++) {
        register int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        add_edge(u,v,d),add_edge(v,u,d);
        for(int j=1; j<=k; ++j) {
            add_edge(u+(j-1)*n,v+j*n,0);
            add_edge(v+(j-1)*n,u+j*n,0);
            add_edge(u+j*n,v+j*n,d);
            add_edge(v+j*n,u+j*n,d);
        }//每层之间建边
    }
    for(int i=1; i<=k; ++i) {
        add_edge(t+(i-1)*n,t+i*n,0);//每层终点连边（不一定用K次最优）
    }
    dijkstra();
    printf("%d",dis[k*n+t]);
    return 0;
}

二、线段树dijkstra

523ms / 26.64MB / 1.41KB C++

#include
#include
using namespace std;
const int N=110005,M=2500001;
int n,m,kth,cnt,s,t;
int tr[N<<2],h[N],nxt[M],to[M],w[M],dis[N];
#define R register int
inline int rd() {
    int t=0;
    char c=getchar();
    while(c'9') c=getchar();
    while(c>='0' && c<='9') t=(t<<3)+(t<<1)+(c^48),c=getchar();
    return t;
}
inline void add_edge(int u,int v,int _w) {
    nxt[++cnt]=h[u],to[cnt]=v,w[cnt]=_w,h[u]=cnt;
}
#define min(a,b) (dis[a]<dis[b]? a:b)
inline void modify(int o,int l,int r,int pos,int val) {
    if (l==r) {
        tr[o]=val;
        return;
    }
    int mid=l+r>>1;
    if (pos<=mid) modify(o<<1,l,mid,pos,val);
    else modify(o<<1|1,mid+1,r,pos,val);
    tr[o]=min(tr[o<<1],tr[o<<1|1]);
}
inline void dijkstra() {
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0,modify(1,1,kth*n,s,s);//线段树存点的编号，然后通过比较dis上传
    for (R t=1,u,v; t<kth*n; t++) {
        u=tr[1],modify(1,1,kth*n,u,0);//dis0始终保持0x3f，作为删除操作
        for (R i=h[u]; i; i=nxt[i])
            if (dis[v=to[i]]>dis[u]+w[i])
                dis[v]=dis[u]+w[i],modify(1,1,kth*n,v,v);
    }
}
int main() {
    n=rd(),m=rd(),kth=rd(),s=rd()+1,t=rd()+1;//编号加1，空出dis0的位置
    for (R i=1,u,v,_w; i<=m; i++) {
        u=rd()+1,v=rd()+1,_w=rd();
        add_edge(u,v,_w),add_edge(v,u,_w);
        for(int j=1; j<=kth; ++j) {
            add_edge(u+(j-1)*n,v+j*n,0);
            add_edge(v+(j-1)*n,u+j*n,0);
            add_edge(u+j*n,v+j*n,_w);
            add_edge(v+j*n,u+j*n,_w);
        }
    }
    for (R i=1;i<=kth;i++)
     add_edge(t+(i-1)*n,t+i*n,0);
    kth++;
    dijkstra();
    printf("%d",dis[(kth-1)*n+t]);
    return 0;
}

三、DP最短路

296ms / 2.26MB / 1.15KB C++

这种方法最快，而且数组的范围比较好确定

注意dis，vis，node是二维，要记录点的编号和所用次数

#include
#include
#include
using namespace std;
struct edge {
   int v,w,h;
} e[100010];
int n,m,K,s,t,cnt,ans,h[10010],d[10010][11];
bool vis[10010][11];
struct node {
   int u,k;
   bool operator <(const node &x) const {
       return d[u][k]>d[x.u][x.k];
   }
};
inline void add(int u,int v,int w) {
   e[++cnt]=(edge) {v,w,h[u]},h[u]=cnt;
}
inline void dijkstra() {
   priority_queue q;
   memset(d,0x3f,sizeof d);
   q.push((node) {
       s,0
   }),d[s][0]=0,vis[s][0]=1;//s点，用了0次
   while(!q.empty()) {
       node x=q.top();
       q.pop(),vis[x.u][x.k]=0;
       for (register int i=h[x.u],v,u,k; i; i=e[i].h) {
           if (d[v=e[i].v][k=x.k]>d[u=x.u][k]+e[i].w) {
               d[v][k]=d[u][k]+e[i].w;
               if (!vis[v][k]) q.push((node) {
                   v,k
               }),vis[v][k]=1;
           }//更新不使用的情况，k不变
           if (d[v][k+1]>d[u][k] && k<K) {
               d[v][k+1]=d[u][k];
               if (!vis[v][k+1] && k<K) q.push((node) {
                   v,k+1
               }),vis[v][k+1]=1;
           }//更新使用的情况，k加1且小于K
       }
   }
}
int main() {
   scanf("%d%d%d%d%d",&n,&m,&K,&s,&t);
   for (int i=1,u,v,w; i<=m; i++)
       scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
   dijkstra();
   ans=1e9;
   for (int i=0; i<=K; i++)
       ans=ans<d[t][i]? ans:d[t][i];//用几次最优
   printf("%d",ans);
}