D. Traffic Lights 【Codeforces Round 1038, Div. 1 + Div. 2】

D. Traffic Lights

思路

可以证明从1到n的总时间不超过 $3n$ （见证明）
bfs时间步进模拟​​运动即可，时间复杂度是 $O(n^2)$

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
#define pb emplace_back
#define pii pair<int, int>
#define FU(i, a, b) for (int i = (a); i <= (b); ++i)
#define FD(i, a, b) for (int i = (a); i >= (b); --i)
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int MAXN = 5005;vector<int> G[MAXN];
int d[MAXN];  // 到达节点u的最小等待次数
int nd[MAXN]; // 临时数组，用于存储下一个时间步的状态void solve() {int n, m;cin >> n >> m;for (int i = 0; i <= n; i++) {G[i].clear();}FU(i, 1, m) {int u, v;cin >> u >> v;G[u].pb(v);G[v].pb(u);}memset(d, INF, sizeof(int) * (n + 2));d[1] = 0;int tm = 0;while (d[n] >= INF) {// 等待for (int j = 1; j <= n; j++) {nd[j] = d[j] + 1;}// 移动for (int j = 1; j <= n; j++) {if (d[j] == INF)continue;int nx = G[j][tm % G[j].size()];if (d[j] < nd[nx]) {nd[nx] = d[j];}}memcpy(d, nd, sizeof(int) * (n + 2));tm++;}cout << tm << " " << d[n] << '\n';
}signed main() {
#ifndef ONLINE_JUDGEfreopen("../in.txt", "r", stdin);
#endif// cin.tie(0)->ios::sync_with_stdio(0);int T = 1;cin >> T;while (T--) {solve();}return 0;
}