<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个节点的有向有边权的完全图上进行:  
<ol>
<li>游戏一共有n个步骤</li>
<li>在第i步, 小黄从图中移除掉一个节点以及与该节点相连的所有入边和出边(移除后的图仍然是一个完全图)</li>
<li>在每一步小黄移除一个节点之前, 他想知道所有节点对之间的最短路径的总和是多少</li>
</ol>
<p>{% raw %}<br>
</div><br>
<div class="part" title="Input"><br>
{% endraw %}</p>
<p>输入为小黄游戏之前的图:<br>
第一行: n(1&lt;=n&lt;=400), 表示图的节点个数;<br>
接下来一共n行为一个n*n的矩阵, 矩阵的每行n个数, 第i行的第j列的数字a(1≤a≤?50000表示从节点i到节点j的边的边权, 其中节点i到节点i自身的边权都是0;<br>
最后n行一行一个1到n之间的数, 其中的第i行表示第i步小黄要移除的节点编号.</p>
<p>{% raw %}<br>
</div><br>
<div class="part" title="Output"><br>
{% endraw %}</p>
<p>输出一共一行n个数(一个空格隔开), 分别为第i步移除节点之前的所有节点对的最短路径总和.</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<br>
0 3 1 1<br>
6 0 400 1<br>
2 4 0 1<br>
1 1 1 0<br>
4 1 2 3</p>
<p>{% raw %}<br>
</div><br>
<div class="output part" title="Sample Output"><br>
{% endraw %}</p>
<p>17 23 404 0</p>
<p>{% raw %}<br>
</div><br>
<div class="clear"></div><br>
</div><br>
</div></p>
</div></div>
{% endraw %}

<h1 id="heading-1">题解</h1>
<p>很好的一道题,算法是很简单的算法,但是需要有一定的理解</p>
<p>Floyd 是一个很容易被忽视的算法,因为它实在是太简单了<br>
只需要三个循环就能完成多源最短路<br>
尽管时间复杂度较高,但是多源最短路也没有其他更好的算法了</p>
<p>其本质是动态规划<br>
以</p>
<pre style="background-color:#fff"><span style="font-weight:bold">for</span>(<span style="color:#458;font-weight:bold">int</span> k<span style="font-weight:bold">=</span><span style="color:#099">0</span>;k<span style="font-weight:bold">&lt;</span>n;k<span style="font-weight:bold">++</span>)
    <span style="font-weight:bold">for</span>(<span style="color:#458;font-weight:bold">int</span> i<span style="font-weight:bold">=</span><span style="color:#099">0</span>;i<span style="font-weight:bold">&lt;</span>n;i<span style="font-weight:bold">++</span>)
        <span style="font-weight:bold">for</span>(<span style="color:#458;font-weight:bold">int</span> j<span style="font-weight:bold">=</span><span style="color:#099">0</span>;j<span style="font-weight:bold">&lt;</span>n;j<span style="font-weight:bold">++</span>)
            dis[i][j] <span style="font-weight:bold">=</span> min(dis[i][j],dis[i][k] <span style="font-weight:bold">+</span> dis[k][j]);
</pre><p>为例<br>
<code>i</code> 和 <code>j</code> 只是为了便利整个图,不属于动态规划的算法部分<br>
重点看 <code>k</code><br>
这就是精华所在, <code>k</code> 的意义为,<strong>前 <code>k</code> 个点的最短路</strong><br>
那么,答案已经出来了,将删点看作加点,按照删除的逆序把点加入到图中,每次都只需要计算已经加入到图中的点的最短路和</p>
<p>在 Floyd 上已经坑过两次了,最简单的反而最容易忽视<br>
比赛的时候已经想到了删点变为加点,不过没有细想 k 的意义,最后每加一个点都跑一次 Floyd 果断超时<br>
想了只更新新加的点可能影响到的部分,还是基础功不扎实的锅</p>
<h1 id="heading-2">代码</h1>
<div><div class="fold_hider"><div class="close hider_title">点击显/隐代码</div></div><div class="fold">```cpp 最短路径和 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
/*/
#define debug
#include <ctime>
//*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
<p>const int maxn = 405;<br>
const int INF = 0x3f3f3f;<br>
int del[maxn];<br>
int dis[maxn][maxn];<br>
int ans[maxn];</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;
while(cin &gt;&gt; n){
    for(int i=0;i&lt;n;i++)
        for(int j=0;j&lt;n;j++)
            cin &gt;&gt; dis[i][j];

    for(int p=0;p&lt;n;p++){
        cin &gt;&gt; del[p];
        del[p]--;
    }
        

    for(int p=n-1;p&gt;=0;p--){
        int k = del[p];
        for(int i=0;i&lt;n;i++)
            for(int j=0;j&lt;n;j++)
                    dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);

        // cout &lt;&lt; endl;
        // for(int i = 0;i &lt; n;i++){
        //     for(int j = 0;j &lt; n;j++)
        //         cout &lt;&lt; dis[i][j] &lt;&lt;&quot; &quot;;
        //     cout &lt;&lt; endl;
        // }
        // cout &lt;&lt; endl;
        

        ans[p] = 0;
        for(int i=p;i&lt;n;i++)
            for(int j=p;j&lt;n;j++)
                    ans[p] += dis[del[i]][del[j]];
    }
    for(int i=0;i&lt;n;i++){
        if(i)
            cout &lt;&lt; &quot; &quot;;
        cout &lt;&lt; ans[i];
    }
    cout &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 841.最短路径和