教育投资网站建设方案,wordpress提醒用法,阿里巴巴官网登录,益阳网站开发G. Moving to the Capital
先bfs一边#xff0c;求出距1号点的最短路用数组d1[]记录#xff0c;求的过程中如果当前点t遍历到之前遍历过的点j意味着这条边就是能够拉近与1号点距离的边#xff08;横向边或者后向边#xff09;那么就用d1[j]更新d2[t]#xff0c;d2[]表示最…G. Moving to the Capital
先bfs一边求出距1号点的最短路用数组d1[]记录求的过程中如果当前点t遍历到之前遍历过的点j意味着这条边就是能够拉近与1号点距离的边横向边或者后向边那么就用d1[j]更新d2[t]d2[]表示最终求得答案。
然后反向边建图从上面bfs的叶子节点开始就像“拨叶子”一样更新d2[]
注意反向建图跑bfs的更新条件
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeset
#includemap
#includecmath
#includestack
#includequeue
#includerandom
#includebitset
#includestring
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includeunordered_map
#includeunordered_set
using namespace std;
typedef long long ll;
typedef pairint,int pii;
const int N200010,M2*N;
const ll mod1e97;
int n,m;
int h1[N],h2[N],e[M],ne[M],idx;
int d1[N],d2[N];
bool st[N],in[N];
void add(int h[],int a,int b)
{e[idx]b,ne[idx]h[a],h[a]idx;
}
queueint q;
void bfs()
{for(int i1;in;i)in[i]st[i]0,d1[i]-1,d2[i]0x3f3f3f3f;d1[1]d2[1]0;q.push(1);while(q.size()){int tq.front();q.pop();int cnt0;for(int ih1[t];i!-1;ine[i]){int je[i];if(d1[j]!-1){d2[t]min(d2[t],d1[j]);continue;}cnt;d1[j]d2[j]d1[t]1;q.push(j);}if(!cnt) st[t]1;}for(int i1;in;i)if(st[i]) {q.push(i);in[i]1;}while(q.size()){int tq.front();q.pop();in[t]0;for(int ih2[t];i!-1;ine[i]){int je[i];if(d1[t]d1[j]){d2[j]min(d2[t],d2[j]);if(!in[j]) q.push(j);in[j]1;}}}
}
int main()
{IO;int T1;cinT;while(T--){cinnm;for(int i1;in;i) h1[i]h2[i]-1;idx0;while(m--){int a,b;cinab;add(h1,a,b);add(h2,b,a);}bfs();for(int i1;in;i) coutd2[i] ;cout\n;}return 0;
}要加油哦~
