Codeforces Codeforces Round #693 (Div. 3). G. Moving to the Capital
原题链接
中等
作者:
Anoxia_3
,
2021-01-14 21:13:01
,
所有人可见
,
阅读 418
G. Moving to the Capital
bfs+记忆化搜索
#include <iostream>
#include <cstring>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#define INF 0x3f3f3f3f
#define fi first
#define se second
using namespace std;
typedef long long LL ;
typedef pair<int , int> PII;
const int N = 200010;
int e[N] , ne[N] , h[N] , idx;
int d[N] , f[N];
int n , m;
vector<int> a[N] , b[N];
void add(int a , int b)
{
e[idx] = b , ne[idx] = h[a] , h[a] = idx++;
}
void bfs()
{
queue<int> q;
q.push(1);
d[1] = 0;
while(q.size())
{
int t = q.front();
q.pop();
for(int i = h[t] ; ~i ; i = ne[i])
{
int j = e[i];
if(d[j] == -1)
{
d[j] = d[t] + 1;
q.push(j);
}
}
}
}
int dfs(int u)
{
if(~f[u]) return f[u];
f[u] = d[u];
//走实边,随便走
for(int x : a[u])
f[u] = min(f[u] , dfs(x));
//走虚边
/*当通过虚边走到点x时,不会再走了,证明如下:
假设走向点是y点,因为无法再向d值更小点走,即无法走向1点,所以只会向d值更大的点走,
如果向d值更大的点走,最终的答案一定会比当前的大。
*/
for(int x : b[u])
f[u] = min(f[u] , d[x]);
return f[u];
}
void solve()
{
cin >> n >> m;
for(int i = 1 ; i <= n ; i++)
a[i].clear() , b[i].clear();
memset(d , -1 , sizeof d);
memset(h , -1 , sizeof h);
memset(f , -1 , sizeof f);
while(m--)
{
int a , b;
cin >> a >> b;
add(a , b);
}
//先通过bfs预处理出1点到其他所有点的最短路程
bfs();
//将每个点的出边划分为实边和虚边
for(int x = 1 ; x <= n ; x++)
for(int i = h[x] ; ~i ; i = ne[i])
{
int j = e[i];
if(d[x] < d[j]) a[x].push_back(j);//实边
else b[x].push_back(j);//虚边
}
//通过记忆化搜索求出答案
for(int i = 1 ; i <= n ; i++)
if(f[i] == -1)
f[i] = dfs(i);
for(int i = 1 ; i <= n ; i++)
cout << f[i] << ' ';
cout << endl;
}
int main()
{
int T = 1;
cin >> T;
for(int turn = 1 ; turn <= T ; turn++)
solve();
}