<h1 id="heading">题目</h1>
<p>{% raw %}</p>
<div><div class="fold_hider"><div class="close hider_title">点击显/隐题目</div></div><div class="fold">
    <div class="oj">   
        <div class="part" title="Description">
{% endraw %}
每当西瓜的朋友来西瓜家看他，西瓜总是喜欢带他们逛自己的豪宅。西瓜的豪宅有N幢楼（1<=N<=1000），用1到N的整数编号。1号楼是西瓜豪宅的大门，N号楼是西瓜的储藏室。西瓜的豪宅里总共有M条道路（1<=M<=10000）。每条道路连接两栋不同的楼房，道路的长度不超过35000。  
为了最好地炫耀他的豪宅，西瓜准备从大门出发，经过一些楼房到达储藏室，再经过一些楼房回到自己的大门。  
他要求他的路径越短越好，但是不能经过任意一条道路多于一次。请你计算这样的一条最短路径。西瓜保证这样的路径是存在的。  
<p>{% raw %}<br>
</div><br>
<div class="part" title="Input"><br>
{% endraw %}</p>
<p>第一行：N和M<br>
第2..M+1行：每行三个整数表示一条道路（起点，终点，长度）</p>
<p>{% raw %}<br>
</div><br>
<div class="part" title="Output"><br>
{% endraw %}</p>
<p>一个整数，表示最短路径长度</p>
<p>{% raw %}<br>
</div><br>
<div class="samp"><br>
<div class="clear"></div><br>
<div class="input part" title="Sample Input"><br>
{% endraw %}</p>
<p>4 5<br>
1 2 1<br>
2 3 1<br>
3 4 1<br>
1 3 2<br>
2 4 2</p>
<p>{% raw %}<br>
</div><br>
<div class="output part" title="Sample Output"><br>
{% endraw %}</p>
<p>6</p>
<p>{% raw %}<br>
</div><br>
<div class="clear"></div><br>
</div><br>
</div></p>
</div></div>
{% endraw %}

<h1 id="heading-1">题解</h1>
<p>本次最难的一题<br>
要求是对于一个无向图,在每条路只走一次的情况下,从起点到终点再返回起点的最短路<br>
看到最短路,很容易就想到 BFS ,由于每条路有一定的权值,因此需要用 Dijkstra</p>
<p>很显然的思路,而且能通过样例<br>
但是如果仔细分析样例就能发现有很大的问题存在<br>
<div class='image'><a href='//static.oyohyee.com/post/aoj835.png' target='_blank' rel='noopener noreferrer'><img src="//static.oyohyee.com/post/aoj835.png" /></a></div></p>
<p>可以很容易看出来,去的时候最短路是 3<br>
回来的时候最短路也是 3</p>
<p>但是,如果单纯只是删掉第一次最短路途径的边去跑第二次最短路,有可能就会出现问题<br>
比如,如果第一次最短路走的是 <code>1-2-3-4</code> 这条路,那么第二次时压根就无法返回起点</p>
<p>也就是说,<strong>存在有多个最短路有重边的情况</strong><br>
这个问题导致了单纯的搜是不行的</p>
<p><strong>图论问题,不会不如试下网络流</strong></p>
<p>套用网络流的概念来分析下试试</p>
<ul>
<li>最短路 = 最小费用</li>
<li>每个边一次 = 流量为1</li>
</ul>
<p>看上去好像没有问题,再深入分析下<br>
最小费用的是 <strong>最小费用最大流</strong><br>
它求的是在所有最大流中费用最小的</p>
<p>那么我们先要限定流量<br>
由于每个边只能走一次,边的流量显然是 1<br>
如何体现去回两次呢?<br>
可以在建一个源点,这个源点往外的流量为 2 ,将它连在起点或终点上,然后跑它到另一个点的最小费用最大流</p>
<p>由于其他点的流量都是 1 ,这个节点往外的流量是 2 ,因此只要有解,最大流必然为 2<br>
此时建的图已经和题意的图存在一些差别了<br>
可以看作从起点走两条完全不同的路(每条路的流量为 1 )到终点(汇点流量为 2 )</p>
<p>建图完毕,套用模板</p>
<p>匡斌的模板里点的编号是 <code>0~n-1</code><br>
因此加边的时候要把 u 和 v 分别减去 1<br>
初始化的时候记得加上汇点</p>
<p>输出最小的费用即可</p>
<h1 id="heading-2">代码</h1>
<div><div class="fold_hider"><div class="close hider_title">点击显/隐代码</div></div><div class="fold">```cpp FJ的旅行 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
/*/
#define debug
#include <ctime>
//*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
<p>const int MAXN = 1005;<br>
const int MAXM = 10005;<br>
const int INF = 0x3f3f3f3f;<br>
struct Edge {<br>
int to,next,cap,flow,cost;<br>
}edge[MAXM];</p>
<p>int head[MAXN],tol;<br>
int pre[MAXN],dis[MAXN];<br>
bool vis[MAXN];<br>
int N;//节点总个数，节点编号从0~N-1<br>
void init(int n){<br>
N = n;<br>
tol = 0;<br>
memset(head,-1,sizeof(head));<br>
}<br>
void addedge(int u,int v,int cap,int cost) {<br>
edge[tol].to = v;<br>
edge[tol].cap = cap;<br>
edge[tol].cost = cost;<br>
edge[tol].flow = 0;<br>
edge[tol].next = head[u];<br>
head[u] = tol++;<br>
edge[tol].to = u;<br>
edge[tol].cap = 0;<br>
edge[tol].cost = -cost;<br>
edge[tol].flow = 0;<br>
edge[tol].next = head[v];<br>
head[v] = tol++;<br>
}<br>
bool spfa(int s,int t) {<br>
queue<int>q;<br>
for(int i = 0;i &lt; N;i++) {<br>
dis[i] = INF;<br>
vis[i] = false;<br>
pre[i] = -1;<br>
}<br>
dis[s] = 0;<br>
vis[s] = true;<br>
q.push(s);<br>
while(!q.empty()){<br>
int u = q.front();<br>
q.pop();<br>
vis[u] = false;<br>
for(int i = head[u]; i != -1;i = edge[i].next){<br>
int v = edge[i].to;<br>
if(edge[i].cap &gt; edge[i].flow &amp;&amp;<br>
dis[v] &gt; dis[u] + edge[i].cost ){<br>
dis[v] = dis[u] + edge[i].cost;<br>
pre[v] = i;<br>
if(!vis[v]){<br>
vis[v] = true;<br>
q.push(v);<br>
}<br>
}<br>
}<br>
}<br>
if(pre[t] == -1)return false;<br>
else return true;<br>
}<br>
//返回的是最大流，cost存的是最小费用<br>
int minCostMaxflow(int s,int t,int &amp;cost) {<br>
int flow = 0;<br>
cost = 0;<br>
while(spfa(s,t)){<br>
int Min = INF;<br>
for(int i = pre[t];i != -1;i = pre[edge[i^1].to]){<br>
if(Min &gt; edge[i].cap - edge[i].flow)<br>
Min = edge[i].cap - edge[i].flow;<br>
}<br>
for(int i = pre[t];i != -1;i = pre[edge[i^1].to]){<br>
edge[i].flow += Min;<br>
edge[i^1].flow -= Min;<br>
cost += edge[i].cost * Min;<br>
}<br>
flow += Min;<br>
}<br>
return flow;<br>
}</p>
<p>int main(){<br>
#ifdef debug<br>
freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);<br>
int START = clock();<br>
#endif<br>
cin.tie(0);<br>
cin.sync_with_stdio(false);</p>
<pre><code>int n, m;
while(cin&gt;&gt;n&gt;&gt;m){
    init(n+1);
    for(int i=0;i&lt;m;i++){
        int u,v,cost;
        cin &gt;&gt; u &gt;&gt; v &gt;&gt; cost;
        addedge(u-1,v-1,1,cost);
        addedge(v-1,u-1,1,cost);
    }
    addedge(n-1,n,2,0);
    int ans=0;
    minCostMaxflow(0,n,ans);
    cout &lt;&lt; ans &lt;&lt; endl;
}

#ifdef debug
printf(&quot;Time:%.3fs.\n&quot;, double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;
</code></pre>
<p>}</p>
<pre style="background-color:#fff">&lt;/div&gt;</pre>

AOJ 835.FJ的旅行