购物网站设计公司,合肥建站免费模板,360推广怎么收费,佛山网站seoE - Escape from the Island
大佬题解#xff0c;码风真的爱了
状态表式#xff1a;f(u,j)f(u,j)f(u,j)当前在uuu点#xff0c;已经划了jjj步时离终点的最短距离 状态转移#xff1a; 主动划一步min#xff0c;转移到下一个点vvv f(u,j)f(v,j1)1,(u,v)∈E,(u,v)∈Ef(u,j…E - Escape from the Island
大佬题解码风真的爱了
状态表式f(u,j)f(u,j)f(u,j)当前在uuu点已经划了jjj步时离终点的最短距离 状态转移 主动划一步min转移到下一个点vvv f(u,j)f(v,j1)1,(u,v)∈E,(u,v)∈Ef(u,j)f(v,j1)1,(u,v)\in E,(u,v)\in Ef(u,j)f(v,j1)1,(u,v)∈E,(u,v)∈E 顺着水流漂max转移到下一个点vvv f(u,j)f(v,0)1,(u,v)∈Ef(u,j)f(v,0)1,(u,v)\in Ef(u,j)f(v,0)1,(u,v)∈E
由于我们知道最终点的状态即f(n,j)0f(n,j)0f(n,j)0于是考虑bfs倒着进行更新 主动划一步(v,j1)→(u,j)(v,j1)\to(u,j)(v,j1)→(u,j) 顺水漂一步(v,0)→(u,j)(v,0)\to(u,j)(v,0)→(u,j)
非常dt就是顺水飘是最长路更新而bfs是最短路更新 比如从(u,j)→(v1,0),(v2,0)…(vk,0)(u,j)\to(v_1,0),(v_2,0)\dots(v_k,0)(u,j)→(v1,0),(v2,0)…(vk,0)划了一步在bfs过程中会始终让离终点最近的点先出队不妨设出队顺序为(v1,0),(v2,0)…(vk,0)(v_1,0),(v_2,0)\dots(v_k,0)(v1,0),(v2,0)…(vk,0)即默认f(v1,0)≤f(v2,0)≤⋯≤f(vk,0)f(v_1,0)\leq f(v_2,0)\leq \dots \leq f(v_k,0)f(v1,0)≤f(v2,0)≤⋯≤f(vk,0)我们只需要让最后出队的点(vk,0)(v_k,0)(vk,0)更新(u,j)(u,j)(u,j)即可也就是记录一下uuu的出度当出度为0是就是最后的那个一个点对其进行更新。
对于无出边的情况我们让其原地更新
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeset
#includemap
#includecmath
#includestack
#includequeue
#includebitset
#includerandom
#includebitset
#includestring
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includeunordered_map
#includeunordered_set
using namespace std;
typedef long long ll;
typedef pairll,int pli;
typedef pairint,int pii;
const int N100010,M200010;
int h[N],e[M],ne[M],idx;
int d[N];
bool nd[N];
void add(int a,int b)
{e[idx]b,ne[idx]h[a],h[a]idx;
}
int f[N][55];
int n,m,k;
void init()
{memset(h,-1,sizeof(int)*(n1));idx0;memset(d,0,sizeof(int)*(n1));memset(nd,0,sizeof(bool)*(n1));for(int i1;in;i)for(int j0;jk;j)f[i][j]0x3f3f3f3f;
}
queuepii q;
void update(int a,int b,int c,int d)
{if(f[c][d]0x3f3f3f3f)f[c][d]f[a][b]1,q.push({c,d});
}
void bfs()
{for(int i0;ik;i)f[n][i]0,q.push({n,i});while(q.size()){auto [u,t]q.front();q.pop();if(t0)for(int ih[u];i!-1;ine[i])update(u,t,e[i],t-1);else{ // t0for(int ih[u];i!-1;ine[i]){ //0代表顺着水流 1代表逆这水流if(i%20) continue; //倒着更新需要逆着水流 --d[e[i]];if(!d[e[i]])for(int j0;jk;j)update(u,t,e[i],j);}if(nd[u])for(int j0;jk;j)update(u,t,u,j);}}
}
int main()
{IO;int T1;cinT;for(int ca1;caT;ca){cinnmk;init();for(int i1;im;i){int u,v;cinuv;add(u,v),add(v,u);d[u];}for(int i1;in;i)if(!d[i]) nd[i]1;//没有出度bfs();printf(Case #%d:\n,ca);for(int i1;in;i)printf(%d\n,(f[i][0]0x3f3f3f3f?-1:f[i][0]));}return 0;
}要加油哦~
