题目大意：

从1到n再回来，每条边只能走一次，问最短路。

——————————————————

如果不告诉我是费用流打死不会想这个……

我们把问题简化为1到n跑两遍，然后每条边容量为1，费用为长度。

然后建一个s和t，s到1容量为2，n到t容量为2.

跑费用流。

（注意，本题是双向边～！）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long ll;const int INF=1e9;const int maxn=1010;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct node{ int nxt; int to; int w; int b;}edge[50010];int head[maxn],cnt=-1;void add(int u,int v,int w,int b){ cnt++; edge[cnt].to=v; edge[cnt].w=w; edge[cnt].b=b; edge[cnt].nxt=head[u]; head[u]=cnt; return;}int dis[maxn];bool vis[maxn];inline bool spfa(int s,int t,int n){ deque
           
            q; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++)dis[i]=INF; dis[t]=0;q.push_back(t);vis[t]=1; while(!q.empty()){ int u=q.front(); q.pop_front();vis[u]=0; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; int b=edge[i].b; if(edge[i^1].w&&dis[v]>dis[u]-b){ dis[v]=dis[u]-b; if(!vis[v]){ vis[v]=1; if(!q.empty()&&dis[v]