大致题意:
给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。
大致思路:
最短路稍稍变形,加入一个val限制即可
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax=3050;
const int mMax=1000050;
const int inf=1<<28;
struct{
int v, next;
int w,val;
}edge[mMax];
int n, k, edgeHead[nMax],rehead[nMax],rk;
int dis[nMax],issea[nMax];
int stack[nMax],m,val[nMax];
bool vis[nMax];
void addedge(int a,int b,int w,int val){
edge[k].w = w;
edge[k].v=b;
edge[k].val=val;
edge[k].next=edgeHead[a];
edgeHead[a]=k;k++;
}
int spfa(int s){
int i, top = 0;
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++){
dis[i]=inf;
val[i]=inf;
}
dis[s]=0;
val[s]=0;
stack[++top]=s;
vis[s]=true;
while(top){
int u=stack[top--];
vis[u]=false; /////////////////
for(i=edgeHead[u];i!=0;i=edge[i].next){
int v=edge[i].v;
if(dis[v]>dis[u]+edge[i].w){
dis[v]=dis[u]+edge[i].w;
val[v]=val[u]+edge[i].val;
if(!vis[v]){
vis[v]=true;
stack[++top] = v;
}
}
if(dis[v]==dis[u]+edge[i].w&&val[v]>val[u]+edge[i].val){
dis[v]=dis[u]+edge[i].w;
val[v]=val[u]+edge[i].val;
if(!vis[v]){
vis[v]=true;
stack[++top] = v;
}
}
}
}
int sum=0;
for(i=1;i<=n;i++){
sum+=dis[i];
}
return sum;
}
int main(){
int i,j,s,t,a,b,c,d;
while(scanf("%d%d",&n,&m)&&(n||m)){
k=1;
memset(edgeHead,0,sizeof(edgeHead));
while(m--){
scanf("%d%d%d%d",&a,&b,&c,&d);
addedge(a,b,c,d);
addedge(b,a,c,d);
}
scanf("%d%d",&s,&t);
spfa(s);
cout<<dis[t]<<" "<<val[t]<<endl;
}
return 0;
}
分享到:
相关推荐
包含图论众多热点问题:最短路径——Dijkstra SPFA Floyd等 最小生成树的两种计算方法、三种中心度、连通分量的计算 输入文件格式按照graph_movie.txt
这个是关于SPFA最短路径一些相关东西。。
T005_最短路径SPFA算法,SPFA最短路径
NULL 博文链接:https://128kj.iteye.com/blog/1716385
现在网上有很多最短路径的算法,C++版本的较多,java可用的demo较少,或者不支持双向的,这里总结了java版的spfa算法,个人认为此算法比较实用(拓扑、GIS定位等项目上),本算法支持双向,有兴趣的可以下载下来研究...
求单源点最短路径效率很高的spfa算法,包括2个样例程序和测试数据。
NULL 博文链接:https://128kj.iteye.com/blog/1716609
从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径,称为最短路径此处运用了SPFA的算法,可以解决单源最短路径
第 29 卷2期1 9 9 4年4月关于最短路径的 S P F A 快速算法段凡 丁(西南交通 大学计算中心成都【摘要】【关 键词】【分 类号】本文 提出 了关
SPFA[知乎:叶枝黎曼].py
最短路径问题(python实现) 解决最短路径问题:(如下三种算法) (1)迪杰斯特拉算法(Dijkstra算法) (2)弗洛伊德算法(Floyd算法) (3)SPFA算法 第一种算法: Dijkstra算法 广度优先搜索解决赋权有向图或者...
SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称,通常用于求含负权边的单源最短路径,以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同,为 O(VE)。
一个求最短路径的代码,用spfa算法做的
详细描述了解决最短路径问题的方法,包括:Dijkstra算法,Bellman-Ford算法 SPFA算法,以及一些习题。
蓝桥杯CJ2-11-图论最短路径问题 Bellman-Ford算法+SPFA.pdf
spfa的算法思想(动态逼近法):设立一个先进先出的队列q用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对离开u点所指向的结点v
SPFA的讲解、有一个简单的例子模拟了算法执行的整个过程、 代码实现及打印最淡路径
无向图或有向图单个源点到其他顶点的最短路径算法(采用邻接表存储)
SPFA实现的最短路径问题,找两点之间的最短路径。可移植性较好