题解 | 神经网络信号传播预测

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

const int N = 105;
const int inf = 0x3f3f3f3f;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int m, n, e[N][N];
int edx, edy, dist[N][N];
bool st[N][N];

struct node {
    int dis, x, y;
    bool operator < (const node & t) const {
		return this -> dis > t.dis;
	}
};

vector<node> ve;

int dij(int x, int y) {
    memset(dist, 0x3f, sizeof dist);
    priority_queue<node>q;
    q.push({0, x, y});
    dist[x][y] = 0;
    while( q.size() ) {
        auto [dis, nowx, nowy] = q.top();
        q.pop();
        // cout << "x = " << nowx << " y = " << nowy << endl;
        if(st[nowx][nowy]) continue;
        st[nowx][nowy] = true;
        for(int i=0; i<4; i++) {
            int tx = nowx + dx[i], ty = nowy + dy[i];
            if(tx<0||tx>=m||ty<0||ty>=n||!e[tx][ty]) continue;
            int d = dis + e[tx][ty];
            if(dist[tx][ty] > d) {
                dist[tx][ty] = d;
                q.push({d, tx, ty});
            }
        }
    }
    int res = inf;
    for(auto &[_,x,y] : ve) {
        res = min(res, dist[x][y]);
    }
    return res;
}

int main() {
    ios :: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> m >> n;
    for(int i=0; i<m; i++) {
        for(int j=0; j<n; j++) {
            cin >> e[i][j];
        }
    }
    
    int x;
    vector<int> v;
    while( cin >> x ) {
        v.emplace_back(x);
    }
    edy = v.back(); v.pop_back();
    edx = v.back(); v.pop_back();

    if(!e[edx][edy]) {
        cout << -1;
        return 0;
    }

    for(int i=0; i<v.size()-1; i+=2) {
        ve.push_back({0, v[i], v[i + 1]});
    }
    int res = dij(edx, edy);
    cout << (res == inf ? -1 : res);

    return 0;
}
// 64 位输出请用 printf("%lld")

迪杰斯特拉从终点向起点跑即可；注意反向走的时候边权的意义。