主要是考虑如何转化为网络流问题，要求从起点到终点，再从终点到起点，总的花费最小。相当于从源点到终点走两遍，因为要求每一条边只能走一遍，所以可以以1为每条边的流量，用来限制每一条边只能走一遍，以每条边的路程为花费，再设立一个源点和一个汇点，源点和1号节点之间费用为0，流量为2，n号点和汇点之间的边流量为2，花费为0。注意：因为原图中每一边为双向边，所以每一条边要建两次正向边，两次反向边。（因为这个WA了很久）。
代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N=1e3+5;
const int inf=0x3f3f3f3f;
typedef pair<int,int> P;
queue<int>que;
int dis[N],flow[N];
bool vis[N];
P pre[N];
int n,m,s,t;
struct edge
{
    int to,val,cost,rev;
};
vector<edge>pic[N];
bool spfa()
{
    while(!que.empty())
        que.pop();
    for(int i=s;i<=t;i++)
    {
        dis[i]=inf;
        flow[i]=inf;
        vis[i]=false;
    }
    memset(pre,0,sizeof(pre));
    dis[s]=0;
    que.push(s);
    vis[s]=true;
    while(!que.empty())
    {
        int v=que.front();
        que.pop();
        vis[v]=false;
        for(int i=0;i<pic[v].size();i++)
        {
            edge tmp=pic[v][i];
            if(dis[tmp.to]>dis[v]+tmp.cost&&tmp.val>0)
            {
                dis[tmp.to]=dis[v]+tmp.cost;
                pre[tmp.to].first=v;
                pre[tmp.to].second=i;
                flow[tmp.to]=min(flow[v],tmp.val);
                if(!vis[tmp.to])
                {
                    vis[tmp.to]=true;
                    que.push(tmp.to);
                }
            }
        }
    }
    if(dis[t]<inf)
        return true;
    else
        return false;
}
void EK()
{
    int max_flow=0,min_cost=0;
    while(spfa())
    {
        int f=flow[t];
        for(int i=t;i!=s;i=pre[i].first)
        {
            pic[pre[i].first][pre[i].second].val-=f;
            pic[i][pic[pre[i].first][pre[i].second].rev].val+=f;
        }
        max_flow+=f;
        min_cost+=(f*dis[t]);
    }
    printf("%d\n",min_cost);
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        s=0;
        t=n+1;
        for(int i=s;i<=t;i++)
            pic[i].clear();
        int a,b,c;
        pic[s].push_back({1,2,0,pic[1].size()});
        pic[1].push_back({s,0,0,pic[s].size()-1});
        for(int i=1;i<=m;i++)
        {//因为边为无向边，所以一条边要要建4次边
            scanf("%d%d%d",&a,&b,&c);
            pic[a].push_back({b,1,c,pic[b].size()});
            pic[b].push_back({a,0,-c,pic[a].size()-1});
            pic[b].push_back({a,1,c,pic[a].size()});
            pic[a].push_back({b,0,-c,pic[b].size()-1});
        }
        pic[n].push_back({t,2,0,pic[t].size()});
        pic[t].push_back({n,0,0,pic[n].size()-1});
        EK();
    }
    return 0;
}