【分层图最短路】Rinne Loves Graph

电玩女神 2024-03-24 14:10 104阅读 0赞

[1031-Rinne Loves Graph\_2021秋季算法入门班第九章习题：图论（重现赛）@lamentropetion (nowcoder.com)][1031-Rinne Loves Graph_2021_lamentropetion _nowcoder.com]

题意：

![94f10497b99c4f69a0a87cfe0d109eb6.png][]

思路：

这题和普通最短路唯一的区别是多了个限制条件，因此可以考虑最短路DP，即在原来的最短路基础上加上一维次数，就可以转移了，本质上是分层图最短路

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e3+10;
    const int mxe=1e5+10;
    struct ty{
        int to,next,w;
    }edge[mxe<<1];
    struct ty2{
        int x,dis,c;
        bool operator<(const ty2&a)const{
            return a.dis<dis;
        }
    };
    
    priority_queue<ty2> q;
    int n,m,k,u,v,w,tot=0;
    int a[mxn],head[mxn],dis[mxn][mxn],vis[mxn];
    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 G_init(){
        tot=0;
        for(int i=0;i<=n;i++){
            head[i]=-1;
        }
    }
    void dij(){
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        q.push({1,0,0});
        dis[1][0]=0;
        while(!q.empty()){
            ty2 u=q.top();
            q.pop();
            if(vis[u.x]) continue;
            vis[u.x]=1;
            for(int i=head[u.x];~i;i=edge[i].next){
                int newc=u.c+a[u.x];
                if(newc>k) continue;
                if(dis[edge[i].to][newc]>dis[u.x][u.c]+edge[i].w){
                    dis[edge[i].to][newc]=dis[u.x][u.c]+edge[i].w;
                    q.push({edge[i].to,dis[edge[i].to][newc],newc});
                }
            }
        }
    }
    void solve(){
        cin>>n>>m>>k;
        G_init();
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=m;i++){
            cin>>u>>v>>w;
            add(u,v,w);
            add(v,u,w);
        }
        dij();
        int ans=1e9;
        for(int i=0;i<=k;i++) ans=min(ans,dis[n][i]);
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[1031-Rinne Loves Graph_2021_lamentropetion _nowcoder.com]: https://ac.nowcoder.com/acm/contest/54497/1031
[94f10497b99c4f69a0a87cfe0d109eb6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/b8c2782a5daf4cb08704d81fd2bcb77d.png