HDU4370 0 or 1 神转换，最短路

题目可以转换为1-n的一条最短路，题目的限制，可以理解为n个结点，1的出度为1，n的入度为1，其他点出度等于入度，1代表选这条边，0代表不选，这样就相当于求1-n的最短路。。Orz 神转换。

但是问题在于，除了1-n的最短路，还有1种情况满足条件，那就是，1-1转一个环，n-n转一个环，这样也满足3条限制，所以答案必须是这两种情况的最小值。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          using namespace std; #define INF 0x3f3f3f3f int d[305]; int n; int v[305]; int g[305][305]; void spfa(int st) { int i,u; queue
         
           Q; memset(v,0,sizeof(v)); d[st]=INF; for(i=1;i<=n;i++) { if(i!=st) { v[i]=1; d[i]=g[st][i]; Q.push(i); } } while(!Q.empty()) { u=Q.front();Q.pop(); v[u]=0; for(i=1;i<=n;i++) { if(d[u]+g[u][i]