题解 【AT3677 [ABC079D] Wall】

Solution

我们可以把题目抽象化：就是说现在有从 0 到 9 共十个点，现有 $c_{i,j}$ 表示从 $i$ 到 $j$ 的路径长度为 $c_{i,j}$， 求 $\sum d_{a_{i,j},1}$ ,其中 $d_{i,j}$ 表示从 $i$ 到 $j$ 的最短路。
然而这题只需要到 1 号点，是单元最短路，我们可以用 spfa 来解决。
但是观察数据范围，发现在这个出具范围下， Floyd 也能够跑出优秀的速度，所以偷个懒用 Floyd 就好了。时间复杂度 $\mathcal{O(W\times H)}$

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 209;

int c[N][N],h,w,ans,x;

int main() {
    scanf("%d %d",&h,&w);
    for(int i = 0;i < 10;i++) {
        for(int j = 0;j < 10;j++) scanf("%d",&c[i][j]);
    }
    for(int k = 0;k < 10;k++) {
        for(int i = 0;i < 10;i++) {
            for(int j = 0;j < 10;j++) if(c[i][j] > c[i][k] + c[k][j]) c[i][j] = c[i][k] + c[k][j];
        }
    }
    for(int i = 1;i <= h;i++) {
        for(int j = 1;j <= w;j++) {
            scanf("%d",&x);
            ans += (x == -1) ? 0 : c[x][1];
        }
    }
    printf("%d\n",ans);
    return 0;
}