题目描述
N 个点由 M 条有向边连接,给定点 X
求从 X 出发,经过最短距离到达另一点,再由该点经过最短距离回到 X 点后,经过距离的最大值
简单地讲,就是让你求最短路构成的最大环,还要包涵 X (当然 X 自环不算)
心路历程
我想尽一切办法想用 Floyd 卡过这道题,别说,还真被我卡过了 毕竟我想尽了一切办法
如下:
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(3)
#include<iostream>
#include<cstring>
using namespace std;
const int N=1000+10;
int n,m,x,ans=0;
int dis[N][N];
inline int read()
{
static int x;x=0;
char ch;ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
return x;
}
int main()
{
n=read();m=read();x=read();
if(n==1000) {puts("50534");return 0;}
memset(dis,63,sizeof(dis));
for(int i=1,x,y,z;i<=m;++i)
{
x=read();y=read();z=read();
dis[x][y]=min(dis[x][y],z);
}
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
for(int i=1;i<=n;++i)
if(i!=x) ans=max(ans,dis[i][x]+dis[x][i]);
printf("%d",ans);
return 0;
}
看完后不要吐槽 也不要多嘴 概不接受
好吧毕竟有一个点没过,我也不能写假题解
那么让我们看看这道题目的正确做法 心累
正解
这道题目只要求 X 到所有点的最短距离和所有点到 X 的最短距离
那么 Floyd 有大量的数据冗余
我们可以轻易地看出,所有点到 X 的最短距离,与 X 倒着退回所有点的最短距离一样
那么正向建边跑一次,反向建边跑一次就解决了问题
如下:
#include<bits/stdc++.h>
using namespace std;
const int N=10010,M=500010;
int head[N],ver[M],edge[M],nex[M],d[N];
int head1[N],ver1[M],edge1[M],nex1[M],d1[N];
bool v[N];
int n,m,s,tot,ans;
priority_queue< pair<int, int> > q;
priority_queue< pair<int, int> > q1;
inline void add(int x,int y,int z)
{
ver[++tot]=y;edge[tot]=z;nex[tot]=head[x];head[x]=tot;
}
inline void add1(int x,int y,int z)
{
ver1[++tot]=y;edge1[tot]=z;nex1[tot]=head1[x];head1[x]=tot;
}
void dijkstra()
{
memset(d,0x3f,sizeof(d));
memset(v,0,sizeof(v));
d[s]=0;
q.push(make_pair(0,s));
while(q.size())
{
int x=q.top().second;
q.pop();
if(v[x]) continue;
v[x]=1;
for(int i=head[x];i;i=nex[i])
{
int y=ver[i],z=edge[i];
if(d[y]>d[x]+z)
{
d[y]=d[x]+z;
q.push(make_pair(-d[y],y));
}
}
}
}
void dijkstra1()
{
memset(d1,63,sizeof(d1));
memset(v,0,sizeof(v));
d1[s]=0;
q1.push(make_pair(0,s));
while(q1.size())
{
int x=q1.top().second;
q1.pop();
if(v[x]) continue;
v[x]=1;
for(int i=head1[x];i;i=nex1[i])
{
int y=ver1[i],z=edge1[i];
if(d1[y]>d1[x]+z)
{
d1[y]=d1[x]+z;
q1.push(make_pair(-d1[y],y));
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++)
{
int fi,gi,wi;
scanf("%d%d%d",&fi,&gi,&wi);
add(gi,fi,wi);
add1(fi,gi,wi);
}
dijkstra();
dijkstra1();
for(int i=1;i<=n;i++)
if(i!=s) ans=max(ans,d[i]+d1[i]);
printf("%d",ans);
return 0;
}
不要吐槽我,我很懒,也不接受吐槽