EC-Final 2022 I. Chase Game

警钟长鸣！提交

#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;

ll n,m,k,d,s[(int)3e5+9],now[(int)3e5+9],dep[(int)3e5+9],dis[(int)3e5+9],cost[(int)3e5+9],qsb[(int)3e5+9],ans=1e18;
vector<int> g[(int)1e5+9]; 
bitset<(int)3e5+9> vis;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>k>>d;
    for(int i=1,x,y;i<=m;++i){
        cin>>x>>y;
        g[x].push_back(y),g[y].push_back(x);
    }
    for(int i=1;i<=m;++i){
        s[i]=s[i-1]+d-(i-1)%d;
    }
    for(int i=1;i<=d;++i){
        now[i]=now[i-1]+i;
    }
    {
        queue<int> q;
        q.push(n);
        dis[n]=1;
        while(!q.empty()){
            auto p=q.front();q.pop();
            for(auto it:g[p])if(!dis[it])dis[it]=dis[p]+1,q.push(it);
        }
    }
    {
        queue<int> q;
        q.push(k);
        dep[k]=d;
        while(!q.empty()){
            auto p=q.front();q.pop();
            for(auto it: g[p]){
                if(!dep[it]){
                    dep[it]=dep[p]-1;
                    if(dep[it])q.push(it);
                }
            }
        }
    }
    {
        priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>q;
        q.push({0,1});
        memset(cost,0x3f,sizeof(cost));
        cost[1]=0ll;
        while(!q.empty()){
            auto [aa,bb]=q.top();q.pop();
            if(vis[bb])continue;
            vis[bb]=1;
            for(auto it:g[bb]){
                if(dep[it]){
                    if(cost[it]>cost[bb]+dep[it]){
                        cost[it]=cost[bb]+dep[it];
                        q.push({cost[it],it});
                    }
                }else if(!vis[it]) ans=min(ans,cost[bb]+s[dis[it]]);
                //cerr<<ans<<"::"<<bb<<"-->"<<it<<"????"<<dep[it]<<"\n";
            }
        }
    }
    ans=min(ans,cost[n]);

    cout<<ans;
    return 0;
}