牛客网NOIP赛前集训营 第6场 T1 最长路

【题解】

　　先建反向图，然后跑拓扑排序求出最长路。

　　将所有的点按照最长路从小到大分层，把上一层连向这一层的边按照边权为第一关键字、起点的排名为第二关键字排序。

　　按照这个顺序更新这一层的答案，按照这一层每个点被更新的顺序得到这一层的点的排名。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define LL long long

 #define rg register

 #define N 1000010

 #define Mod (998244353)

 using namespace std;

 int n,m,tot,cnt,last[N],in[N],dis[N],q[N],rk[N],ans[N];

 struct edge{int to,pre,dis;}e[N];

 struct poi{int dis,num;}p[N];

 struct rec{int w,rk,from,to;}r[N];

 inline int read(){

     int k=,f=; char c=getchar();

     while(c<''||c>'')c=='-'&&(f=-),c=getchar();

     while(''<=c&&c<='')k=k*+c-'',c=getchar();

     return k*f;

 }

 inline bool cmp(rec a,rec b){

     if(a.w==b.w) return a.rk<b.rk;

     return a.w<b.w;

 }

 inline bool cmp2(poi a,poi b){return a.dis<b.dis;}

 inline void topu(int x){

     int front=,rear=; q[]=x;

     while(front<rear){

         int now=q[++front];

         for(rg int i=last[now],to;i;i=e[i].pre){

             to=e[i].to;

             dis[to]=max(dis[to],dis[now]+);

             if(!(--in[to])) q[++rear]=to;

         }

     }

 }

 int main(){

     n=read(); m=read();

     for(rg int i=;i<=m;i++){

         int u=read(),v=read(),d=read(); in[u]++;

         e[++tot]=(edge){u,last[v],d}; last[v]=tot;

     }

     for(rg int i=;i<=n;i++)if(!in[i]&&!dis[i]) topu(i);

     for(rg int i=;i<=n;i++){

         p[i].num=i;

         if(in[i]) p[i].dis=2e9; else p[i].dis=dis[i];

     }

     sort(p+,p++n,cmp2);

     int st=,ed=;

     while(st<=n){

         tot=;

         while(p[ed].dis==p[st].dis&&ed<=n){

             int now=p[ed].num;

 //            printf("now=%d ed=%d\n",now,ed);

             for(rg int i=last[now],to;i;i=e[i].pre){

                 if(dis[to=e[i].to]==dis[now]+) r[++tot]=(rec){e[i].dis,rk[now],now,to};

             }

             ed++;

         }

         sort(r+,r++tot,cmp);

         for(rg int i=;i<=tot;i++)if(!ans[r[i].to]){

 //            printf("%d %d %d %d %d\n",r[i].to,r[i].from,r[i].w,ans[r[i].from],ans[r[i].to]);

             ans[r[i].to]=(1ll*ans[r[i].from]*+r[i].w*)%Mod;

             rk[r[i].to]=++cnt;

         }

         st=ed;

     }

     for(rg int i=;i<=n;i++) if(in[i]>) puts("Infinity"); else printf("%d\n",ans[i]%Mod);

     return ;

 }