The 2023 ICPC Asia Hangzhou Regional Contest（G. Snake Move（最短路））

Snake Move - Problem - QOJ.ac

考虑最短路

因为我们只移动蛇头，后续蛇身的移动到其他位置时并不影响那个位置的答案，所以只需要考虑蛇身所在初始位置所带来的影响：

对于移动操作可以看成：每走一步，蛇身长度-1(蛇尾往前进一位)；

按步数大小排序，每次取出步数最小的点，然后更新当前的蛇身长度，用这个点去更新其他点

1.如果没有撞到蛇身和障碍，直接更新当前距离+1

2.假如在走的过程中撞到蛇身时，可以选择做操作S直到这个蛇身变成蛇尾再走（蛇头可以走向蛇尾），需要的步数是：这个蛇身到当前蛇尾的距离+1

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define endl '\n'
#define pii pair<int, int>
const int N = 1E6 + 10;
const int mod = 998244353;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};struct node
{int d, x, y;bool operator<(const node p) const{return d > p.d;}
};
void solve()
{int n, m, k;cin >> n >> m >> k;vector<node> v(k + 1);                                              // 记录蛇身位置vector<vector<long long>> f(n + 1, vector<long long>(m + 1, 1e18)); // 记录最短路vector<vector<char>> mp(n + 1, vector<char>(m + 1, '1'));           // 存图vector<vector<int>> is(n + 1, vector<int>(m + 1, 0));               // 记录蛇身下标vector<vector<int>> vis(n + 1, vector<int>(m + 1, false));          // 记录点是否被走过for (int i = 1; i <= k; i++){cin >> v[i].x >> v[i].y;is[v[i].x][v[i].y] = i;}for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> mp[i][j];}}priority_queue<node> q;q.push({0, v[1].x, v[1].y});f[v[1].x][v[1].y] = 0;int p = k;while (!q.empty()){auto [d, x, y] = q.top();q.pop();if (vis[x][y])continue;vis[x][y] = 1;while (p > 1 && p != k - d) // 走了多少步，就缩短多少个蛇身长度{is[v[p].x][v[p].y] = 0;p--;}for (int i = 0; i < 4; i++){int nx = x + dx[i];int ny = y + dy[i];if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] == '.'){if (is[nx][ny] == 0 || (nx == v[p].x && ny == v[p].y)) // 这个位置不是蛇身或者是蛇尾，就可以正常走{if (f[nx][ny] > d + 1){f[nx][ny] = d + 1;q.push({d + 1, nx, ny});}}else // 是蛇身{if (f[nx][ny] > d + 1 + p - is[nx][ny]){f[nx][ny] = d + 1 + p - is[nx][ny];q.push({d + 1 + p - is[nx][ny], nx, ny});}}}}}unsigned long long res = 0;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){// cout << f[i][j] << ' ';if (f[i][j] != 1e18)res += (unsigned long long)f[i][j] * (unsigned long long)f[i][j];// res %= (1ll << 64);}// cout << endl;}cout << res << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;// cin >> t;while (t--)solve();
}

理论时间复杂度nmlog(nm)，按理来说最高会跑2e8次，但是由于这是矩阵图，每个点最多连四条边，并且每个点只更新一次所以实际复杂度不高，可以在1s左右通过本题