1874 Bellman-ford算法 队列优化过的 用于稀疏图,有负权的图
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
#define N 2100
struct node {
int u,v,w,next;
}bian[N];
int n,m,yong,head[N];
void creat(int u,int v,int w) {
bian[yong].u=u;
bian[yong].v=v;
bian[yong].w=w;
bian[yong].next=head[u];
head[u]=yong++;
}
void Dcreat(int u,int v,int w) {
creat(u,v,w);
creat(v,u,w);
}
int Bellman-ford(int u,int s) {
int cur,dis[N],i,visit[N],v;
queue<int>q;
memset(visit,0,sizeof(visit));
for(i=0;i<n;i++)
dis[i]=1000000000;
dis[u]=0;
q.push(u);
visit[u]=1;
while(!q.empty()) {
u=q.front();
q.pop();
visit[u]=0;
for(i=head[u];i!=-1;i=bian[i].next) {
v=bian[i].v;
if(dis[v]>bian[i].w+dis[u]) {
dis[v]=bian[i].w+dis[u];
if(!visit[v]) {
visit[v]=1;
q.push(v);
}
}
}
}
for(i=0;i<yong;i++)//判断是否存在负权路
if(dis[bian[i].v]>dis[bian[i].u]+bian[i].w)//
return -1;
if(dis[s]<1000000000)
return dis[s];
return -1;
}
int main() {
int a,b,k;
while(scanf("%d%d",&n,&m)!=EOF) {
yong=0;
memset(head,-1,sizeof(head));
while(m--) {
scanf("%d%d%d",&a,&b,&k);
Dcreat(a,b,k);
}
scanf("%d%d",&a,&b);
printf("%d\n",Bellman-ford(a,b));
}
return 0;
}
最新文章
- [BZOJ4197][Noi2015]寿司晚宴
- vmstat和iostat
- CCNET+MSBuild+SVN实现每日构建
- 2014鸟人Birdman中文字幕文件下载
- Photoshop投影和CSS box-shadow转换
- The Swift Programming Language 中文翻译版(个人翻新随时跟新)
- I.MX6 ubuntu-core-14.04 Apache php mysql Qt5
- 64.OV7725初始化配置
- 使用Keil建立工程和烧录到89C52板上
- Trunk Club:颠覆男士时装零售的创业公司_第1页_福布斯中文网
- Debian 安装 vmware-tools 手记
- laravel5.4 后台RBAC功能完成中遇到的问题及解决方法
- Angular创建路由从主界面跳转到我们的cesium界面
- 获取请求Url
- Spring Boot 2 (三):Spring Boot 2 相关开源软件
- Day Seven
- 将Web项目War包部署到Tomcat服务器
- 【Ubuntu】全局代理
- 适配器模式(PHP实现)
- python 模块导入全局变量
热门文章
- bzoj 1651: [Usaco2006 Feb]Stall Reservations 专用牛棚【贪心+堆||差分】
- bzoj 1618: [Usaco2008 Nov]Buying Hay 购买干草【背包】
- P4244 [SHOI2008]仙人掌图 II
- 【知识总结】多项式全家桶(三)(任意模数NTT)
- linux学习之路5 系统常用命令
- Win7上安装Oracle数据库
- Java对象简单实用(计算器案例)
- Python,报错NameError: name &#39;math&#39; is not defined
- Elasticsearch--预匹配器
- sqlalchemy.exc.InvalidRequestError: Entity &#39;<;class &#39;model.TestCase&#39;>;&#39; has no property &#39;project&#39;