【[SDOI2009]Elaxia的路线】

魏佬告诉我跑得快不一定赢，不跌跟头才是成功

我决定把这句话作为魏佬的名言记下来

等以后人人捧着魏佬语录的时候，我可以告诉他们魏佬从小就开始向我传授人生经验

但我就是跑的快，而且非常快

成功卡到了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;

}

巴特西

【[SDOI2009]Elaxia的路线】

最新文章

热门文章