【SPFA,DIJ】Day 12向上組模擬C組T 4バリケードブロック

リンク
https://www.luogu.org/problemnew/show/P2865
テーマの大意
負の重みのない無方向図を与えて二次短絡を求める
問題を解く構想.
ごみ水問題
まず、熊某淇dalaoによると、この問題はテンセント大戦360によく似ているという.
その問題の大意は2つの点を与え,この2つの点に到達する距離と最小の中継点を求めることである.
この問題は2回のSPFA S P F Aで行ったもので,二次短絡についても同様の解法を用いることができ,中間に中継点や辺を列挙し,長さが最短の最長辺より大きくなければならない.
もちろんDIJ D I Jでもデータ水でも負のループがないし、DIJ D I Jでもスタック最適化とフィボナッチスタック最適化が可能で、時間の複雑さも非常に大きい.
コード#コード#

#include
#include
#include
#define N 5001
#define M 200001
#define re register
#define getchar() (S==T&&(T=(S=BB)+fread(BB,1,1<<15,stdin),S==T)?EOF:*S++)
using namespace std;int f,n,m,x,y,w,ans=2147483647,l[N],tot,dis_s[N],dis_t[N],SP;
struct node{int next,to,w;}e[M];
char c;
queue<int>q;
bool vis[N];
inline void add(re int u,re int v,re int w)
{
    e[++tot]=(node){l[u],v,w};l[u]=tot;
    e[++tot]=(node){l[v],u,w};l[v]=tot;
    return;
}
char BB[1<<15],*S=BB,*T=BB;
inline int read() 
{
    f=0;
    while(c=getchar(),c<=47||c>=59);f=(f<<3)+(f<<1)+c-48;
    while(c=getchar(),c>=48&&c<=57) f=(f<<3)+(f<<1)+c-48;
    return f;
}
inline void spfa(re int S,re int *dis)//spfa
{
    while(q.size()) q.pop();
    q.push(S);vis[S]=true;dis[S]=0;
    while(q.size())
    {
        int x=q.front();q.pop();vis[x]=true;
        for(re int i=l[x];i;i=e[i].next)
        {
            int y=e[i].to,w=e[i].w;
            if(dis[x]+wif(!vis[y]) vis[y]=true,q.push(y);
            }
        }
        vis[x]=false;
    }
    return;
}
signed main()
{
    freopen("block.in","r",stdin);
    freopen("block.out","w",stdout);
    n=read();m=read();
    for(re int i=0;imemset(dis_s,0x3f3f3f3f,sizeof(dis_s));
    memset(dis_t,0x3f3f3f3f,sizeof(dis_t));
    spfa(1,dis_s);
    memset(vis,0,sizeof(0));//   0
    spfa(n,dis_t);//spfa    
    SP=dis_s[n];//Shortest Path，     
    for(re int i=1;i<=n;i++)
     for(re int j=l[i];j;j=e[j].next)
     {
        y=e[j].to;w=e[j].w;
        if(dis_s[i]+dis_t[y]+w>SP&&dis_s[i]+dis_t[y]+w//         
         ans=dis_s[i]+dis_t[y]+w;
     }
     printf("%d",ans);
}