消息传输-dijkstra

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

int main()
{

    int n, m, sx, sy;
    cin >> n >> m >> sx >> sy;
    vector<int> g(m * n);
    vector<int> d(m * n, INT_MAX);
    for(int i = 0; i < m * n; i ++)
    {
        cin >> g[i];
    }
    d[sx * n + sy] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, sx * n + sy});
    vector<int> dirt = {-n, n, -1, 1};
    while(q.size())
    {
        auto t = q.top();
        q.pop();
        int id = t.second, time = t.first;
        if(time > d[id]) continue;
        for(auto dir :dirt)
        {
            if (id % n == 0 && dir == -1) continue;//左边不能左移
            if ((id + 1) % n == 0 && dir == 1) continue;//右边不能右移
            int cur_id = id + dir, cur_time = time + g[id];
            if(cur_id >= 0 && cur_id < m * n && cur_time < d[cur_id] && g[id] != 0)
            {
                d[cur_id] = cur_time;
                q.push({cur_time, cur_id});
            }
        }
    }
    int res = 0;
    for(int i = 0; i < m * n; i ++)
    {
        if(g[i] != 0) res = max(res, d[i]);
    }
    if(res == INT_MAX) cout << -1 << endl;
    else cout << res << endl;
    return 0;
}