[关闭]
@ysner 2020-09-23T20:56:27.000000Z 字数 2222 阅读 1332

【模板】Johnson 全源最短路

负环 最短路


题面

戳我

思考

首先来区分一下
开局不标
用某点更新的条件是
中的表示点是否在队列中。

  1. //SPFA
  2. queue<int>Q;
  3. memset(d,63,sizeof(d));d[0]=0;vis[0]=1;Q.push(0);
  4. while(!Q.empty())
  5. {
  6. int u=Q.front();Q.pop();
  7. for(int i=h[u];i;i=e[i].nxt)
  8. {
  9. int v=e[i].to;
  10. if(d[v]>d[u]+e[i].w)
  11. {
  12. a[v]=a[u]+1;
  13. if(a[v]>n) return 1;//a代表最短路径所含点数,显然不能超过n
  14. d[v]=d[u]+e[i].w;
  15. if(!vis[v]) vis[v]=1,Q.push(v);
  16. }
  17. }
  18. vis[u]=0;//
  19. }
  1. //Dijkstra
  2. priority_queue<node>Q;
  3. for(int i=1;i<=n;i++) dis[i]=1e9,vis[i]=0;
  4. Q.push((node){s,0});dis[s]=0;
  5. while(!Q.empty())
  6. {
  7. int u=Q.top().u;Q.pop();
  8. if(vis[u]) continue;vis[u]=1;//
  9. for(int i=h[u];i;i=e[i].nxt)
  10. {
  11. int v=e[i].to;
  12. if(dis[v]>dis[u]+e[i].w)
  13. {
  14. dis[v]=dis[u]+e[i].w;
  15. if(!vis[v]) Q.push((node){v,dis[v]});
  16. }
  17. }
  18. }

然后不能用于负权图,故只能把图修成正权的。
怎么办?利用,我们可以把边权改成,而这个一定正。
走任意一条路后,可以发现真实距离就是为终点,为起点)。因为中途点的一正一负抵消掉了。

  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. const int N=3e3+3;
  5. struct Edge{int to,nxt,w;}e[N<<2];
  6. struct node{int u,dis;bool operator < (const node &o) const{return dis>o.dis;}};
  7. int n,m,h[N],a[N],cnt;
  8. ll dis[N],d[N],sum;
  9. bool vis[N];
  10. int gi()
  11. {
  12. int x=0,t=1;
  13. char ch=getchar();
  14. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  15. if(ch=='-') t=-1,ch=getchar();
  16. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  17. return x*t;
  18. }
  19. void add(int u,int v,int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}
  20. bool SPFA()
  21. {
  22. queue<int>Q;
  23. memset(d,63,sizeof(d));d[0]=0;vis[0]=1;Q.push(0);
  24. while(!Q.empty())
  25. {
  26. int u=Q.front();Q.pop();
  27. for(int i=h[u];i;i=e[i].nxt)
  28. {
  29. int v=e[i].to;
  30. if(d[v]>d[u]+e[i].w)
  31. {
  32. a[v]=a[u]+1;
  33. if(a[v]>n) return 1;
  34. d[v]=d[u]+e[i].w;
  35. if(!vis[v]) vis[v]=1,Q.push(v);
  36. }
  37. }
  38. vis[u]=0;
  39. }
  40. return 0;
  41. }
  42. void Dijstra(int s)
  43. {
  44. priority_queue<node>Q;
  45. for(int i=1;i<=n;i++) dis[i]=1e9,vis[i]=0;
  46. Q.push((node){s,0});dis[s]=0;
  47. while(!Q.empty())
  48. {
  49. int u=Q.top().u;Q.pop();
  50. if(vis[u]) continue;vis[u]=1;
  51. for(int i=h[u];i;i=e[i].nxt)
  52. {
  53. int v=e[i].to;
  54. if(dis[v]>dis[u]+e[i].w)
  55. {
  56. dis[v]=dis[u]+e[i].w;
  57. if(!vis[v]) Q.push((node){v,dis[v]});
  58. }
  59. }
  60. }
  61. for(int i=1;i<=n;i++)
  62. if(dis[i]==1e9) sum+=i*dis[i];
  63. else sum+=i*(dis[i]+d[i]-d[s]);
  64. printf("%lld\n",sum);sum=0;
  65. }
  66. int main()
  67. {
  68. n=gi();m=gi();
  69. while(m--)
  70. {
  71. int u=gi(),v=gi(),w=gi();
  72. add(u,v,w);
  73. }
  74. for(int i=1;i<=n;i++) add(0,i,0);
  75. if(SPFA()) {puts("-1");return 0;}
  76. for(int u=1;u<=n;u++)
  77. for(int i=h[u];i;i=e[i].nxt)
  78. e[i].w+=(d[u]-d[e[i].to]);
  79. for(int i=1;i<=n;i++)
  80. Dijstra(i);
  81. return 0;
  82. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注