【分层图最短路】JLOI2011 飞行路线

青旅半醒 2024-03-17 17:45 74阅读 0赞

[P4568 \[JLOI2011\] 飞行路线 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P4568 _JLOI2011_ _ - _ _ _ _luogu.com.cn]

题意：

![172039aa2d1a48f99795fb3d76645686.png][]

![4d63a59194f24e899d89a481738f7c9c.png][]

思路：

因为多了一维约束，因此可以在dij的基础上多一维cnt表示已经免费了多少次，然后跑最短路即可

Code：

#include <bits/stdc++.h>
    
    //#define int long long
    
    using namespace std;
    
    const int mxn=1e4+10;
    const int mxe=5e4+10;
    const int mod=1e9+7;
    const int Inf=0x3f3f3f3f;
    
    struct ty{
        int to,next,w;
    }edge[mxe<<2];
    
    struct ty2{
        int x,dis,cnt;
        bool operator<(const ty2&oth)const{
            return oth.dis<dis;
        }
    };
    
    priority_queue<ty2> Q;
    
    int N,M,K,s,t;
    int u,v,w;
    int tot=0;
    int head[mxn],dis[mxn][12],vis[mxn][12];
    
    void G_init(){
        tot=0;
        for(int i=0;i<=N;i++){
            head[i]=-1;
        }
    }
    void add(int u,int v,int w){
        edge[tot].w=w;
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void dij(){
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        Q.push({s,0,0});
        dis[s][0]=0;
        while(!Q.empty()){
            auto u=Q.top();
            Q.pop();
            if(vis[u.x][u.cnt]) continue;
            vis[u.x][u.cnt]=1;
            for(int i=head[u.x];~i;i=edge[i].next){
                //免费
                if(u.cnt<K){
                    if(dis[edge[i].to][u.cnt+1]>dis[u.x][u.cnt]){
                        dis[edge[i].to][u.cnt+1]=dis[u.x][u.cnt];
                        Q.push({edge[i].to,dis[edge[i].to][u.cnt+1],u.cnt+1});
                    }
                }
                //花费
                if(dis[edge[i].to][u.cnt]>dis[u.x][u.cnt]+edge[i].w){
                    dis[edge[i].to][u.cnt]=dis[u.x][u.cnt]+edge[i].w;
                    Q.push({edge[i].to,dis[edge[i].to][u.cnt],u.cnt});
                }
            }
        }
    }
    void solve(){
        cin>>N>>M>>K;
        G_init();
        cin>>s>>t;
        for(int i=1;i<=M;i++){
            cin>>u>>v>>w;
            add(u,v,w);
            add(v,u,w);
        }
        dij();
        int ans=Inf;
        for(int i=0;i<=K;i++){
            ans=min(ans,dis[t][i]);
        }
        cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[P4568 _JLOI2011_ _ - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P4568
[172039aa2d1a48f99795fb3d76645686.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/9a35507c5eb145a7894574f049c19af9.png
[4d63a59194f24e899d89a481738f7c9c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/bedfd724884543d09dda1421839e5307.png