题意

n个点m条无向有权边(2 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5)，每个点标记了0或1，求所有1中，最近的两个1的下标及距离。

题解

先用SPFA求出每个点离标记1的点最近的距离，d[i]。

同时记录下每个点最近的1的下标。

两个最近的1，要么是被一条边连着，要么是被几个0隔着的边连着。

我们通过寻找它们中间的边来找出它们。

枚举每条边，如果相邻都是1，或者都是0且最近的1不是同一个，或者一个1，一个0，那么这条边两个端点的最近1的距离，就可以拿来更新答案。

需要long long。

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define inf 0x3f3f3f3f3f3f3f3f#define N 100005#define ll long longusing namespace std;typedef pair
          
            PII;vector
           
             edge[N<<1];int n,m,a[N];ll d[N];int near[N];bool b[N];queue 
            
              q;void SPFA(){ for(int i=1;i<=n;++i)if(!d[i]) { q.push(i); b[i]=true; near[i]=i; } while(!q.empty()){ int u=q.front(); q.pop(); b[u]=false; for(int j=0;j
             
              w){ ans=w; ansa=i; ansb=to; } }else if(near[i]!=near[to]){ if(ans>d[i]+d[to]+w){ ans=d[i]+d[to]+w; ansa=near[i]; ansb=near[to]; } } } if(ans!=inf)printf("%lld\n%d %d",ans,ansa,ansb); else puts("No luck at all"); return 0;}