思路:
- 关键是操作2的性质: 随机找->找一个路径最长的点
- 操作1,阻止建边顾名思义,
- 发现和最短路很想, 从n到每一个点的权值嘛
- 改变权值更新方式, 边的权值为: val[i]+前面那个点是第几大的, (这里每一个出度的点都要算) ->满足题目要求
- 然后 这个第几大,利用出度来优化, 更新一个后就du- - ;
#pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; #define fir first #define sec second #define mkp make_pair #define pb emplace_back #define For(i,j,k) for(int i=(j),i##_=(k);i<=i##_;i++) #define Rof(i,j,k) for(int i=(j),i##_=(k);i>=i##_;i--) #define ckmx(a,b) a=max(a,b) #define ckmn(a,b) a=min(a,b) #define Fi(s) freopen(s,"r",stdin) #define Fo(s) freopen(s,"w",stdout) #define Fre(s) Fi(s".in"),Fo(s".out") #define debug cerr<<"Line#"<<__LINE__<<endl #define ll long long const ll mod=1; inline ll pw(ll x,ll y){ll r=1;while(y){if(y&1)r=r*x%mod;x=x*x%mod;y>>=1;}return r;} #define int long long #define N 200010 const int inf=1e9; struct node{ int id,dis; friend bool operator<(node x,node y){ return x.dis>y.dis; } }; int dis[N],deg[N],n,m; priority_queue<node> q; vector<int> e[N]; int32_t main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin>>n>>m; For(i,1,n) dis[i]=inf; dis[n]=0; int x,y; For(i,1,m){ cin>>x>>y; e[y].pb(x); deg[x]++; } q.push({n,dis[n]}); while(!q.empty()){ x=q.top().id; y=q.top().dis; q.pop(); if(dis[x]!=y) continue; for(int i:e[x]){ if(dis[x]+deg[i]<dis[i]){ dis[i]=dis[x]+deg[i]; q.push({i,dis[i]}); } deg[i]--; } } cout<<dis[1]<<endl; return 0;}