【最短路dij】牛客练习赛112D qsgg and Subway

骑猪看日落 2024-03-16 22:21 84阅读 0赞

[D-qsgg and Subway\_牛客练习赛112 (nowcoder.com)][D-qsgg and Subway_112 _nowcoder.com]

题意：

![a1727db54b7146fe989c2a2e5dfcb004.png][]

思路：

**感觉这类题难的地方就是更新v的那个值比较难求**

![765860c203434accaea0cd3352fc0e1e.png][]

思路：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int Inf=0x3f3f3f3f;
    
    struct ty{
        int to,next,w1,w2;
    }edge[mxe<<2];
    
    struct ty2{
        int x,dis;
        bool operator<(const ty2&a)const{
            return a.dis<dis;
        }
    };
    
    priority_queue<ty2> q;
    
    int N,M,S,k,t;
    int tmp,x,tot=0;
    int head[mxn],dis[mxn],vis[mxn];
    
    void add(int u,int v,int w1,int w2){
        edge[tot].w1=w1;
        edge[tot].w2=w2;
        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;
        }
    }
    int ceil(int l,int p){
        return (l+p-1)/p;
    }
    void dij(){
        memset(dis,-1,sizeof(dis));
        memset(vis,0,sizeof(vis));
        dis[S]=0;
        q.push({S,0});
        while(!q.empty()){
            ty2 u=q.top();
            q.pop();
            for(int i=head[u.x];~i;i=edge[i].next){
                int w=0;
                int s=edge[i].w1,t=edge[i].w2;
                if(s>=dis[u.x]) w=s+1;
                else w=ceil(dis[u.x]-s,t)*t+s+1;
                if(dis[edge[i].to]>w||dis[edge[i].to]==-1){
                    dis[edge[i].to]=w;
                    q.push({edge[i].to,dis[edge[i].to]});
                }
            }
        }
    }
    void solve(){
        cin>>N>>M>>S;
        G_init();
        for(int i=1;i<=M;i++){
            cin>>k>>t;
            int tmp=0,s=0;
            for(int j=1;j<=k;j++){
                cin>>x;
                if(tmp){
                    add(tmp,x,s,t);
                    s++;
                }
                tmp=x;
            }
        }
        dij();
        for(int i=1;i<=N;i++) cout<<dis[i]<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0; 
    }

[D-qsgg and Subway_112 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/59717/D
[a1727db54b7146fe989c2a2e5dfcb004.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/8bdac625703e467abd0e8a9bc1f3de29.png
[765860c203434accaea0cd3352fc0e1e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/deae998e0c624d949c6eafb3cbb2f810.png