P4568 [JLOI2011]飞行路线

谁借莪１个温暖的怀抱￠ 2023-06-04 07:58 217阅读 0赞

[**题目链接**][Link 1]

**这道题有55分都是最短路板子。但是我们肯定不满足于55分，看了题解才知道这道题是一个叫分层图最短路的东西。**

**对于k次免费机会，相当于建了k层图，每一层的图都是原图上的边权，但是每一层之间所连的边权为0，并且是有向边，我的理解是，因为我们只有一次机会，没有反悔？洛谷上的大佬说的是因为这样才满足dag的性质。**

**代码如下，其实还是很好理解的：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+7;
    int n,m,k,s,t,x,y,v;
    struct node{
        int nxt,to,val;
    }edge[maxn*3];
    int head[maxn],cnt;
    void add(int x,int y,int v){
        edge[++cnt].nxt=head[x];
        edge[cnt].to=y;
        edge[cnt].val=v;
        head[x]=cnt;
    }
    priority_queue<pair<int,int> >q;
    int vis[maxn];
    long long ans;
    bool can[1550][1550];
    long long dis[maxn];
    void dijkstra(int x){
        memset(dis,88,sizeof(dis));
        memset(vis,false,sizeof(vis));
        dis[x]=0;
        q.push(make_pair(0,x));
        while(q.size()){
            int u=q.top().second;
            q.pop();
            if(vis[u]) continue;
            vis[u]=true;
            for(int i=head[u];i;i=edge[i].nxt){
                int go=edge[i].to;
                if(dis[go]>dis[u]+edge[i].val){
                    dis[go]=dis[u]+edge[i].val;
                    q.push(make_pair(-dis[go],go));
                }
            }
        }
    }
    int main(){
        scanf("%d%d%d",&n,&m,&k);
        scanf("%d%d",&s,&t);
        s++,t++;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&x,&y,&v);
            x++,y++;
            add(x,y,v);add(y,x,v);
            for(int j=1;j<=k;j++){
                add(x+(j*n),y+(j*n),v);
                add(y+(j*n),x+(j*n),v);
                add(x+(j-1)*n,y+(j*n),0);
                add(y+(j-1)*n,x+(j*n),0);
            }
        }
        for(int i=1;i<=k;i++) add(t+(i-1)*n,t+(i*n),0);
        dijkstra(s);
        printf("%d\n",dis[t+k*n]);
        return 0;
    }

**推荐几道分层图的模板题：**

[**P4822 BejingWC冻结**][P4822 BejingWC]

[**P2939 \[USACO09FEB\]改造路Revamping Trails**][P2939 _USACO09FEB_Revamping Trails]

转载于:https://www.cnblogs.com/LJB666/p/11628157.html

[Link 1]: https://www.luogu.org/problem/P4568
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/d9b66648b1ab47a297968da48889758b.png
[P4822 BejingWC]: https://www.luogu.org/record/24778098
[P2939 _USACO09FEB_Revamping Trails]: https://www.luogu.org/problem/P2939