魏佬告诉我跑得快不一定赢，不跌跟头才是成功
我决定把这句话作为魏佬的名言记下来
等以后人人捧着魏佬语录的时候，我可以告诉他们魏佬从小就开始向我传授人生经验
但我就是跑的快，而且非常快
成功卡到了b站最优解第五
突然这是我的最后一篇题解了
下午就初赛了，要退役了
好慌啊，好慌啊，好慌啊，我要退役了，退役了，退役了，退役了
好慌啊，好慌啊，好慌啊，我要退役了，退役了，退役了，退役了
好慌啊，好慌啊，好慌啊，我要退役了，退役了，退役了，退役了
这道题其实不难的
首先我们得明确一点，这两个人赢能一起走的路肯定在最短路的公共边上
所以我们肯定得求出最短路的公共边
所以上来就先四遍(Dij)，以这四个点为源点分别跑一遍最短路
之后我们再枚举所有的边，把那些最短路上的公共边建到一张新图里去
之后就有一个性质了，这两个人赢一起走的路径一定是连续的
毕竟两个人赢在一起了怎么会主动分开呢
所以建出新图来之后一遍记搜找出最长连续路径就好了
代码
#include<queue>
#include<cstring>
#include<cstdio>
#include<bitset>
#include<iostream>
#define re register
#define maxn 1505
#define mp std::make_pair
#define max(a,b) ((a)>(b)?(a):(b))
typedef std::pair<int,int> pii;
struct Edge
{
int v,nxt,w;
}e[1500*1500],E[1500*1500];
int head[maxn],d[4][maxn];
int Head[maxn];
int dp[maxn];
std::bitset<maxn> f;
int n,m,x1,y1,x2,y2,num;
int ans;
inline char gc()
{
static char buff[1000000],*S=buff,*T=buff;
return S==T&&(T=(S=buff)+fread(buff,1,1000000,stdin),S==T)?EOF:*S++;
}
inline int read()
{
char c=gc();
int x=0;
while(c<'0'||c>'9') c=gc();
while(c>='0'&&c<='9')
x=(x<<3)+(x<<1)+c-48,c=gc();
return x;
}
inline void add_edge(int x,int y,int z)
{
e[++num].v=y;
e[num].nxt=head[x];
e[num].w=z;
head[x]=num;
}
inline void connect(int x,int y,int z)
{
E[++num].v=y;
E[num].nxt=Head[x];
E[num].w=z;
Head[x]=num;
}
inline void Dij(int s,int o)
{
memset(d[o],20,sizeof(d[o]));
d[o][s]=0;
f.reset();
std::priority_queue<pii,std::vector<pii>,std::greater<pii> > q;
q.push(mp(d[o][s],s));
while(!q.empty())
{
int k=q.top().second;
q.pop();
if(f[k]) continue;
f[k]=1;
for(re int i=head[k];i;i=e[i].nxt)
if(d[o][e[i].v]>d[o][k]+e[i].w)
{
d[o][e[i].v]=d[o][k]+e[i].w;
q.push(mp(d[o][e[i].v],e[i].v));
}
}
}
int dfs(int x)
{
if(dp[x]) return dp[x];
for(re int i=Head[x];i;i=E[i].nxt)
dp[x]=max(dp[x],E[i].w+dfs(E[i].v));
return dp[x];
}
int main()
{
n=read(),m=read();
x1=read(),y1=read(),x2=read(),y2=read();
int x,y,z;
for(re int i=1;i<=m;i++)
x=read(),y=read(),z=read(),add_edge(x,y,z),add_edge(y,x,z);
Dij(x1,0),Dij(x2,1),Dij(y1,2),Dij(y2,3);
num=0;
for(re int i=1;i<=n;i++)
for(re int j=head[i];j;j=e[j].nxt)
if(d[0][i]+e[j].w+d[2][e[j].v]==d[0][y1]&&(d[1][e[j].v]+e[j].w+d[3][i]==d[1][y2]||d[1][i]+e[j].w+d[3][e[j].v]==d[1][y2]))
connect(i,e[j].v,e[j].w);
for(re int i=1;i<=n;i++)
ans=max(ans,dfs(i));
std::cout<<ans;
return 0;
}