spfa代码
先来贴一下,,虽然不是自己写的
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define Maxn 100
#define Maxm 10000
#define Max 10000
using namespace std;
int used[Maxn],outqueue[Maxn],head[Maxn],low[Maxn],n,m;
struct Edge
{
int to,w,next;
}edge[Maxm];
bool SPFA (int start)
{
queue a;
used[start] = 1;
low[start] = 0;
a.push(start);
while (!a.empty())
{
int top = a.front();
a.pop();
outqueue[top]++;
if (outqueue[top] > n) return false;
for (int k = head[top]; k!= -1; k = edge[k].next)
{
if (low[edge[k].to] > low[top] + edge[k].w)
low[edge[k].to] = low[top] + edge[k].w;
if (!used[edge[k].to])
{
used[edge[k].to] = 1;
a.push(edge[k].to);
}
}
}
return true;
}
int main()
{
while (scanf ("%d%d", &n ,&m) != EOF)
{
memset (used, 0 ,sizeof(used));
memset (head, -1 ,sizeof(head));
memset (outqueue, 0 ,sizeof(outqueue));
memset (low, Max, sizeof(low));
int k = 0;
while (m--)
{
int a,b,w;
scanf ("%d%d%d", &a, &b, &w);
edge[k].to = b;
edge[k].w = w;
edge[k].next = head[a];
head[a] = k++;
}
if (SPFA(1))
printf ("%d\n", low[n]);
else
printf ("不存在最短\n");
}
}
最新文章
- js学习之函数的参数传递
- Python 开源网上商城项目
- Shodan新手入坑指南
- linux文件分割(将大的日志文件分割成小的)
- 【网络收集】order by 自定义排序
- 【Javascript下载文件的Post实现】
- Javascript:由 “鸭子类型” 得出来的推论
- ABAP CDS Table Function介绍与示例
- mybatis_SQL映射(1)
- notes for python简明学习教程(1)
- [转]Java Web笔记:搭建环境和项目配置(MyEclipse 2014 + Maven + Tomcat)
- I/O dempo
- yii2 rules验证规则,ajax验证手机号码是否唯一
- BZOJ 3744 Gty的妹子序列 (分块 + BIT)
- Ms17-010进行WEB提权之实践下某培训靶机服务器
- 基于I2C总线的0.96寸OLED显示屏驱动
- Filberder教程
- win7下memCache安装过程
- c语言中函数的形参test(int *&;a)?
- [转][html]大文件下载