luogu2149 Elaxia的路线 (dijkstra+拓扑dp)

先标记上一个人所有最短路上的边（同时也要标记反向边）

然后拿着另一个人最短路上的边（会构成一个DAG）去做拓扑dp，记从原点到某个点的最大的某个路径的被标记的边的个数

 #include<bits/stdc++.h>

 #define pa pair<int,int>

 #define CLR(a,x) memset(a,x,sizeof(a))

 using namespace std;

 typedef long long ll;

 const int maxn=;

 inline ll rd(){

     ll x=;char c=getchar();int neg=;

     while(c<''||c>''){if(c=='-') neg=-;c=getchar();}

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

     return x*neg;

 }

 struct Edge{

     int a,b,l,ne;

     bool u;

 }eg[maxn*maxn];

 int egh[maxn],ect=;

 int N,M,s1,s2,t1,t2;

 int d1[maxn],d2[maxn],ine[maxn],cnt[maxn];

 bool flag[maxn];

 priority_queue<pa,vector<pa>,greater<pa> > q;

 queue<int> q2;

 inline void adeg(int a,int b,int c){

     eg[++ect].a=a,eg[ect].b=b,eg[ect].l=c,eg[ect].ne=egh[a],egh[a]=ect;

 }

 inline void dijkstra(int *dis,int s){

     CLR(flag,);

     dis[s]=;q.push(make_pair(,s));

     while(!q.empty()){

         int p=q.top().second;q.pop();

         if(flag[p]) continue;

         flag[p]=;

         for(int i=egh[p];i;i=eg[i].ne){

             int b=eg[i].b;

             if(dis[b]>dis[p]+eg[i].l){

                 dis[b]=dis[p]+eg[i].l;

                 q.push(make_pair(dis[b],b));

             }

         }

     }

 }

 int main(){

     //freopen("","r",stdin);

     int i;

     N=rd(),M=rd(),s1=rd(),t1=rd(),s2=rd(),t2=rd();

     for(i=;i<=M;i++){

         int a=rd(),b=rd(),c=rd();

         adeg(a,b,c);adeg(b,a,c);

     }

     CLR(d1,);CLR(d2,);

     dijkstra(d1,s1);dijkstra(d2,t1);

     for(i=;i<=ect;i++){

         if(d1[eg[i].a]+eg[i].l+d2[eg[i].b]==d1[t1])

             eg[i].u=eg[i^].u=;

     }

     CLR(d1,),CLR(d2,);

     dijkstra(d1,s2);dijkstra(d2,t2);

     // for(i=1;i<=N;i++) printf("~%d %d %d\n",i,d1[i],d2[i]);

     for(i=;i<=ect;i++){

         if(d1[eg[i].a]+eg[i].l+d2[eg[i].b]==d1[t2])

             ine[eg[i].b]++;

     }

     q2.push(s2);

     while(!q2.empty()){

         int p=q2.front();q2.pop();

         // printf("!%d\n",p);

         for(int i=egh[p];i;i=eg[i].ne){

             int b=eg[i].b;

             if(d1[p]+eg[i].l+d2[eg[i].b]!=d1[t2]) continue;

             cnt[b]=max(cnt[b],cnt[p]+eg[i].u*eg[i].l);

             ine[b]--;

             if(!ine[b]) q2.push(b);

         }

     }

     printf("%d\n",cnt[t2]);

     return ;

 }