[关闭]
@zzzc18 2017-11-10T03:28:46.000000Z 字数 1218 阅读 405

DFS_SPFA

最短路


SPFA算法的优化及应用.pdf467.2kB


深搜版的
使用贪心预处理以及迭代加深,可以得出一个高效的深搜
具体细节可以直接看上面的论文

  1. #include<queue>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<climits>
  6. using namespace std;
  7. typedef long long LL;
  8. const int MAXN = 10000+9;
  9. const int MAXM = 500000+9;
  10. int n,m;
  11. struct E{
  12. int next,to;
  13. LL val;
  14. }edge[MAXM];
  15. int head[MAXN],edge_num;
  16. int S;
  17. LL dis[MAXN];
  18. void addedge(int x,int y,LL v){
  19. edge[++edge_num].next=head[x];
  20. edge[edge_num].to=y;
  21. edge[edge_num].val=v;
  22. head[x]=edge_num;
  23. }
  24. void Build(){
  25. scanf("%d%d%d",&n,&m,&S);
  26. for(int i=1;i<=m;i++){
  27. int a,b;
  28. LL c;
  29. scanf("%d%d%lld",&a,&b,&c);
  30. addedge(a,b,c);
  31. }
  32. for(int i=1;i<=n;i++)
  33. dis[i]=INT_MAX;
  34. dis[S]=0;
  35. }
  36. bool SPFA_INIT(int x,int step,int lim){
  37. if(step==lim)return true;
  38. for(int i=head[x];i;i=edge[i].next){
  39. if(dis[edge[i].to]>dis[x]+edge[i].val){
  40. dis[edge[i].to]=dis[x]+edge[i].val;
  41. SPFA_INIT(edge[i].to,step+1,lim);
  42. return true;
  43. }
  44. }
  45. return false;
  46. }
  47. void SPFA(int x,int step,int lim){
  48. if(step==lim)
  49. return;
  50. for(int i=head[x];i;i=edge[i].next){
  51. if(dis[edge[i].to]>dis[x]+edge[i].val){
  52. dis[edge[i].to]=dis[x]+edge[i].val;
  53. SPFA(edge[i].to,step+1,lim);
  54. }
  55. }
  56. }
  57. int main(){
  58. Build();
  59. for(int i=0;(1<<i-1)<=n;i++){
  60. int depth=1<<i;
  61. for(int j=1;j<=n;j++){
  62. if(SPFA_INIT(j,0,depth)){
  63. for(int k=1;k<=n;k++){
  64. SPFA(k,0,depth);
  65. }
  66. }
  67. }
  68. }
  69. for(int i=1;i<=n;i++)
  70. printf("%d ",dis[i]);
  71. return 0;
  72. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注