链接：

#include <stdio.h>
int main()
{
    puts("转载请注明出处[vmurder]谢谢");
    puts("网址：blog.csdn.net/vmurder/article/details/44537363");
}

题意：

无向连通图上，$S→T$有若干条最短路，$s→t$也有若干条最短路，搞出来两条最短路，要求重合的尽量长（可以方向不同）。

题解：

spfa处理出这四个点到每个点的最短路，然后枚举求哪些边既在$S→T$某条最短路里，又在$s-→t$的某条最短路里，然后这是个拓扑图，跑最长链。
哎呀没什么可说的么，水题贴代码就好啦。

代码：

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1510
#define M 4500000
#define inf 0x3f3f3f3f
using namespace std;
int S,T,s,t,n,m;
int map[N][N],dist[4][N]; // S T s t
bool in[N];
queue<int>q;
void spfa(int s,int d)
{
    memset(dist[d],0x3f,sizeof dist[d]);
    dist[d][s]=0;
    int i,u;
    q.push(s),in[s]=1;
    while(!q.empty())
    {
        u=q.front(),q.pop(),in[u]=0;
        for(i=1;i<=n;i++)if(map[u][i]<inf)
            if(dist[d][i]>dist[d][u]+map[u][i])
            {
                dist[d][i]=dist[d][u]+map[u][i];
                if(!in[i])q.push(i),in[i]=1;
            }
    }
    return ;
}
struct Eli
{
    int v,len,next;
}e[M];
int head[N],cnt;
inline void add(int u,int v,int len)
{
    e[++cnt].v=v;
    e[cnt].len=len;
    e[cnt].next=head[u];
    head[u]=cnt;
}
int d[N],f[N],ans;
void TP()
{
    int i,u,v;
    for(i=1;i<=n;i++)if(!d[i])q.push(i);
    while(!q.empty())
    {
        u=q.front(),q.pop();
        ans=max(ans,f[u]);
        for(i=head[u];i;i=e[i].next)
        {
            v=e[i].v;
            f[v]=max(f[v],f[u]+e[i].len);
            d[v]--;
            if(d[v]==0)q.push(v);
        }
    }
}
int main()
{
    freopen("test.in","r",stdin);

    int i,j,k;
    int a,b,c;

    scanf("%d%d%d%d%d%d",&n,&m,&S,&T,&s,&t);
    memset(map,0x3f,sizeof map);
    for(i=1;i<=n;i++)map[i][i]=0;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        map[a][b]=map[b][a]=c;
    }
    spfa(S,0),spfa(T,1),spfa(s,2),spfa(t,3);
    for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(i!=j)
        if(dist[0][i]+map[i][j]+dist[1][j]==dist[0][T])
            if(dist[2][i]+map[i][j]+dist[3][j]==dist[2][t])
                add(i,j,map[i][j]),d[j]++;
    for(i=1;i<=n;i++)if(!d[i])q.push(i);
    TP();
    memset(f,0,sizeof f);
    memset(head,0,sizeof head),cnt=0;
    for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(i!=j)
        if(dist[0][i]+map[i][j]+dist[1][j]==dist[0][T])
            if(dist[3][i]+map[i][j]+dist[2][j]==dist[2][t])
                add(i,j,map[i][j]),d[j]++;
    TP();
    printf("%d\n",ans);
    return 0;
}