简答题 适中
#24858

子图最短路

子图最短路

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#include &lt;cstdio&gt; #include &lt;algorithm&gt; using namespace std; const int N = 105; const int mod = 1e9; int n, m; int f[N][N]; int g[N][N]; int ans; int main() {     scanf("%d%d", &amp;n, &amp;m);     for (int i = 1; i &lt;= n; i++)     {         for (int j = 1; j &lt;= n; j++)             f[i][j] = mod;         f[i][i] = 0;     }     for (int i = 1; i &lt;= m; i++)     {         int u, v, w;         scanf("%d%d%d", &amp;u, &amp;v, &amp;w);         f[u][v] = min(f[u][v], w);         f[v][u] = min(f[v][u], w);     }     for (int l = 1; l &lt;= n; l++)     {         for (int i = 1; i &lt;= n; i++)             for (int j = 1; j &lt;= n; j++)                 g[i][j] = f[i][j];         for (int r = l; r &lt;= n; r++)         {             for (int i = 1; i &lt;= n; i++)                 for (int j = 1; j &lt;= n; j++)                     g[i][j] = min(g[i][j], g[i][r] + g[r][j]);             for (int i = l; i &lt;= r; i++)                 for (int j = i; j &lt;= r; j++)                     ans = (ans + g[i][j]) % mod;         }     }     printf("%d\n", ans);     return 0; }</pre>
这道题暂未补解析。