2025迎春杯T3题解
作为 T3 的出题人，很荣幸此题作为此届迎春杯提交次数最多的一题。 由于此题在使用前经过了多次大改，导致题目描述混乱，在此致歉。
读完题目后，容易发现这是一个最短路问题，于是我们可以使用传统的
由于
考虑优化。发现瓶颈在于我们每获得一个新点，都会枚举整个模拟战区中的所有位置，这会使许多点被重复访问，大大增加了复杂度。于是我们可以想到：当可以前往下一个战区时便前往，此时无需枚举。但此种优化效果不明显。
解法一：统一枚举。时间复杂度
int cnt = 0;
for ( int i = 1; i <= q; i ++ )
if(use[x][i] == 1 && !p[x+1][i]) cnt++, use[x+1][i] = 1;
if ( cnt == 0 ) {
ans ++;
for ( int i = 1; i <= q; i ++ )
if(!p[x][i] && !p[x+1][i]) use[x+1][i] = 1;
}解法二：
解法三：
# include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
const int M = 1e6 + 7;
int n, m, p, q; int a[N], b[N], x[N], y[N];
struct edge {
int nxt, v, w;
}e[M << 1];
int h[N << 1], cnt;
inline void add_edge ( int u, int v, int w ) {
e[++cnt].nxt = h[u], e[cnt].v = v, e[cnt].w = w;
h[u] = cnt;
}
map <long long, bool> mp; int dis[M], t[M]; long long ans;
int main () {
ios :: sync_with_stdio(false); cin.tie(0), cout.tie(0);
cin >> p >> q >> n >> m;
for ( int i = 1; i <= n; i ++ ) {
cin >> x[i] >> y[i];
mp[x[i] * q + y[i] - q] = 1;
}
for ( int j = 1; j <= m; j ++ ) cin >> a[j] >> b[j];
for ( int i = 1; i <= p; i ++ ) {
for ( int j = 1; j <= q; j ++ ) {
if ( mp[i * q + j - q] ) continue;
if ( i + 1 <= p && !mp[i * q + j] ) add_edge(i * q + j - q, i * q + j, 1);
if ( i - 1 >= 1 && !mp[i * q + j - 2 * q] ) add_edge(i * q + j - q, i * q - 2 * q + j, 1);
add_edge(i * q + j - q, p * q + i, 0);
add_edge(p * q + i, i * q + j - q, 1);
}
}
for ( int j = 1; j <= p * q + p; j ++ ) t[j] = -1, dis[j] = 1e9;
for ( int j = 0; j < m; j ++ ) {
int k = a[j] * q + b[j] - q;
if ( j == 0 ) k = 1;
deque <int> dq; dq.push_front(k); dis[k] = 0, t[k] = j;
while ( !dq.empty() ) {
int u = dq.front(); dq.pop_front();
for ( int i = h[u]; i; i = e[i].nxt ) {
int v = e[i].v, w = e[i].w;
if( t[v] != j ) t[v] = j, dis[v] = 1e9;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if ( w == 0 ) dq.push_front(v);
else dq.push_back(v);
}
}
}
ans += dis[a[j + 1] * q + b[j + 1] - q];
}
cout << ans << "\n";
return 0;
}
附加问题一：若所有数据范围上限改为
附加问题二：若所有数据范围上限改为