博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【最短路】【spfa】CODEVS 2645 Spore
阅读量:7176 次
发布时间:2019-06-29

本文共 1630 字,大约阅读时间需要 5 分钟。

spfa最短路+判负权回路(是否某个点入队超过n次)。

1 #include
2 #include
3 #include
4 using namespace std; 5 #define M 20001 6 #define N 1001 7 int n,m,x,y,w1,w2; 8 int v[M],en,cnt[N],dis[N],w[M],first[M],next[M]; 9 bool inq[N];10 queue
q;11 void AddEdge(const int &U,const int &V,const int &W)12 {13 v[++en]=V;14 w[en]=W;15 next[en]=first[U];16 first[U]=en;17 }18 bool spfa(const int &s)19 {20 q.push(s); inq[s]=1;21 memset(dis,0x7f,sizeof(dis));22 memset(cnt,0,sizeof(cnt));23 dis[1]=0; cnt[1]=1;24 while(!q.empty())25 {26 int U=q.front();27 for(int i=first[U];i;i=next[i])28 if(dis[v[i]]>dis[U]+w[i])29 {30 dis[v[i]]=dis[U]+w[i];31 if(!inq[v[i]])32 {33 q.push(v[i]);34 if((++cnt[v[i]])>n) return 0;35 inq[v[i]]=1;36 }37 }38 q.pop(); inq[U]=0;39 } return 1;40 }41 int main()42 {43 while(1)44 {45 scanf("%d%d",&n,&m);46 memset(v,0,sizeof(v));47 memset(w,0,sizeof(w));48 memset(first,0,sizeof(first));49 memset(next,0,sizeof(next));50 if(!n) break;51 for(int i=1;i<=m;i++)52 {53 scanf("%d%d%d%d",&x,&y,&w1,&w2);54 AddEdge(x,y,w1); AddEdge(y,x,w2);55 }56 if(spfa(1)&&dis[n]<2000000000) printf("%d\n",dis[n]);57 else puts("No such path");58 }59 return 0;60 }

转载于:https://www.cnblogs.com/autsky-jadek/p/4076281.html

你可能感兴趣的文章
Apache 配置虚拟主机之1--基于名称(name-based)
查看>>
RHEL6下KWrite中文乱码问题的解决方案
查看>>
我的友情链接
查看>>
使用java脚本引擎
查看>>
HttpWebRequest 禁用系统默认代理
查看>>
『摆渡车 斜率优化dp及总结』
查看>>
How to delete Exchange 2010 Mailbox database the specified time
查看>>
运维人员的手机恐惧症
查看>>
CentOS服务器远程桌面解决方案之FreeNX
查看>>
Linux framebuffer测试程序
查看>>
Powershell与运维之系统管理(一)磁盘管理
查看>>
ubuntu配置网卡
查看>>
pydev下的django运行时找不到入口
查看>>
Leopard概述
查看>>
我的友情链接
查看>>
如何将EDM营销运用到移动互联网的浪潮中
查看>>
DotNetTextBox V3.0 所见即所得编辑器控件Ver3.2.6 Free(免费版)
查看>>
rhel6 下删除多余的内核版本
查看>>
八叶一刀流·七之型·无项目需求分析
查看>>
win7 32位安装php redis驱动
查看>>