C20220806T2 枚举计算

有 \(n\) 个点，求从1号点到 \(n\) 号点的最短路径，但有某些点有前驱，必须先到了前驱才能到达这个点，允许有多个点同时出发。 \(n\leq 3000,m\leq 30000\) 。

一看，这不是最短路吗？第二眼，这不是拓扑吗？于是，这道题思路就出来了。首先给每个点计一个 \(mintime\) ，表示最少要花 \(mintime\) 的时间走完自己的前驱，然后每次找一个前驱已经求好的最小点（类似dijkstra），然后将包含它的所有后继更新，并更新最短路径，唯一需要注意的就是在更新最短路时，需要将 \(dis\) 和 \(mintime\) 取 \(max\) ，从而保证每个点都在前驱之后才出发。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp std::make_pair
#define pii std::pair<int,int>
#define chkmin(_A,_B) (_A=std::min(_A,_B))
#define chkmax(_A,_B) (_A=std::max(_A,_B))
//--------------------FastInOut--------------------//
class IO{
    public:
        inline char read(){
            static const int IN_LEN =1<<18|1;
            static char buf[IN_LEN],*s,*t;
            return (s==t)&&(t=(s=buf)+fread(buf, 1, IN_LEN, stdin)),(s==t)?-1:*s++;
        }
        template<typename _Tp>inline IO &operator >>(_Tp &x){
            static char c11, boo;
            for (c11=read(),boo=0;!isdigit(c11);c11=read()) {
                if (c11==-1)
                    return *this;
                boo|=(c11=='-');
            }
            for(x=0;isdigit(c11);c11=read())
                x=x*10+(c11^'0');
            if(boo)
                x=-x;
            return *this;
        }
        inline void push(const char &c) {
            putchar(c);
        }
        template<typename _Tp>inline IO &operator <<( _Tp x){
            if (x<0)
                x=-x,push('-');
            static _Tp sta[35];
            _Tp top=0;
            do{
                sta[top++]=x%10,x/=10;
            }while(x);
            while(top)
                push(sta[--top]+'0');
            return *this;
        }
        inline IO &operator <<(char lastChar){
            push(lastChar);
            return *this; 
        }
}FIO;
 
struct edge{
    int v,w;
    edge(int _v=0,int _w=0){
        v=_v,w=_w;
    }
};
std::vector<edge> e[3005];
std::vector<int> to[3005];
int dis[3005],bj[3005],inn[3005];
int mintime[3005];
int minn,minid;
int n,m;
 
 
void dijkstra(){
    memset(dis,0x3f,sizeof dis);
    memset(bj,0,sizeof bj);
    dis[1]=0;
    for(int z=1;z<=n;++z){
        minn=2e9;
        for(int i=1;i<=n;++i){
            if(bj[i] || inn[i])
                continue;
            if(dis[i]<minn){
                minn=dis[i];
                minid=i;
            }
        }
        bj[minid]=1;
        for(int i=0;i<(int)to[minid].size();++i){
            inn[to[minid][i]]--;
            chkmax(mintime[to[minid][i]],dis[minid]);
            chkmax(dis[to[minid][i]],mintime[to[minid][i]]);
        }
        for(int i=0;i<(int)e[minid].size();++i){
            chkmin(dis[e[minid][i].v],std::max(mintime[e[minid][i].v],dis[minid]+e[minid][i].w));
        }
    }
}
 
int main(){
    FIO>>n>>m;
    for(int i=1,ui,vi,wi;i<=m;++i){
        FIO>>ui>>vi>>wi;
        e[ui].pb(edge(vi,wi));
    }
    for(int i=1,tmp;i<=n;++i){
        FIO>>tmp;
        for(int j=1,di;j<=tmp;++j){
            FIO>>di;
            to[di].pb(i);
        }
        inn[i]=tmp;
    }
     
    dijkstra();
    FIO<<dis[n];
    return 0;
}