L3-037 夺宝大赛

思路

• 多起点最短路
• 好像对于多起点的最短路，都是反着搜索。即从终点向起点搜索，这样搜索一次就可以了
• 这题的坑点：坐标反着给
• 注意是同时到达大本营的队伍成绩不算，不要看到火拼理解成在路上相遇的队伍（-_-）

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 1e3 + 10, M = N * 2;
const int INF = 0x3f3f3f3f3f3f3f3f;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int n, m, edx, edy;
int g[N][N], st[N][N], dist[N][N];
struct node
{
    int x, y;
};
void bfs(int x, int y)
{
    queue<node> q;
    q.push({x, y});
    dist[x][y] = 0;
    while(q.size())
    {
        node t = q.front();
        q.pop();
        int xx = t.x;
        int yy = t.y;
        //cout << xx << ' ' << yy << endl;
        for(int i = 0; i < 4; i ++)
        {
            int nex = xx + dx[i], ney = yy + dy[i];
            if(nex < 1 || nex > n || ney < 1 || ney > m) continue;
            if(st[nex][ney] || g[nex][ney] == 0) continue;
            st[nex][ney] = 1;
            dist[nex][ney] = dist[xx][yy] + 1;
            q.push({nex, ney});
        }
    }
}
signed main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            cin >> g[i][j];
            if(g[i][j] == 2)
            {
                edx = i, edy = j;
            }
        }
    }
    memset(st, 0, sizeof st);
    memset(dist, -1, sizeof dist);
    bfs(edx, edy);
    int t;
    cin >> t;
    map<int, int> mp;
    vector<node> res;
    for(int i = 1; i <= t; i ++)
    {
        int x, y;
        cin >> y >> x;
        mp[dist[x][y]] ++;
        res.push_back({x, y});
    }
    int min_d = INF, id;
    for(int i = 0; i < t ; i ++)
    {
        int x = res[i].x, y = res[i].y;
        if(dist[x][y] == -1 || mp[dist[x][y]] > 1) continue;
        if(dist[x][y] < min_d)
        {
            min_d = dist[x][y];
            id = i + 1;
        }
    }
    if(min_d == INF)
    {
        cout << "No winner.";
    }
    else cout << id << ' ' << min_d << endl;
    return 0;
}