[spfa]香甜的黄油

2024-01-30 06:48
文章标签 spfa 黄油 香甜

本文主要是介绍[spfa]香甜的黄油,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述
农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1<=N<=500)只奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。当然,他将付出额外的费用在奶牛上。
  农夫John很狡猾。像以前的Pavlov,他知道他可以训练这些奶牛,让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声,以至他可以在晚上挤奶。
  农夫John知道每只奶牛都在各自喜欢的牧场(一个牧场不一定只有一头牛)。给出各头牛在的牧场和牧场间的路线,找出使所有牛到达的路程和最短的牧场(他将把糖放在那)

Input
第一行: 三个数:奶牛数N,牧场数(2<=P<=800),牧场间道路数C(1<=C<=1450)
第二行到第N+1行: 1到N头奶牛所在的牧场号
第N+2行到第N+C+1行: 每行有三个数:相连的牧场A、B,两牧场间距离D(1<=D<=255),当然,连接是双向的

Output
一行 输出奶牛必须行走的最小的距离和

分析
这题只需要按正常的spfa思路去思考,然后因为数据很水比较小,所以可以直接枚举spfa开始的端点。
计算完所有最短路径以后,直接累加起来与当前最小的距离和比较
duang的一声
正解出炉

#include <iostream>
#include <cstdio>
using namespace std;
int u[5001],v[5001],w[5001],next[5001],list[5001],a[5001];
int i,j,p,c,n,mi;
int spfa(int s)
{bool b[5001];int state[5001],d[5001];int head=0,tail=1,i,l=0;state[1]=s;for (i=1;i<=p;i++)b[i]=0;for (i=1;i<=p;i++)d[i]=2147483647;d[s]=0;do{head++;i=list[state[head]];while (i>0){if (d[u[i]]+w[i]<d[v[i]]){d[v[i]]=d[u[i]]+w[i];if (!b[v[i]]){b[v[i]]=1;tail++;state[tail]=v[i];}}i=next[i];}b[state[head]]=0;}while (head!=tail);for (i=1;i<=n;i++)l+=d[a[i]];return l;
}
int main()
{scanf("%d%d%d",&n,&p,&c);for (i=1;i<=n;i++)scanf("%d",&a[i]);for (i=1;i<=c;i++){j++;scanf("%d%d%d",&u[j],&v[j],&w[j]);next[j]=list[u[j]];list[u[j]]=j;j++;u[j]=v[j-1];v[j]=u[j-1];w[j]=w[j-1];next[j]=list[u[j]];list[u[j]]=j;}mi=2147483647;for (i=1;i<=p;i++)mi=min(mi,spfa(i));printf("%d",mi);
}

这篇关于[spfa]香甜的黄油的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/659405

相关文章

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3159 (spfa差分约束最短路) poj 1201

poj 3159: 题意: 每次给出b比a多不多于c个糖果,求n最多比1多多少个糖果。 解析: 差分约束。 这个博客讲差分约束讲的比较好: http://www.cnblogs.com/void/archive/2011/08/26/2153928.html 套个spfa。 代码: #include <iostream>#include <cstdio>#i

poj 3169 spfa 差分约束

题意: 给n只牛,这些牛有些关系。 ml个关系:fr 与 to 牛间的距离要小于等于 cost。 md个关系:fr 与 to 牛间的距离要大于等于 cost。 隐含关系: d[ i ] <= d[ i + 1 ] 解析: 用以上关系建图,求1-n间最短路即可。 新学了一种建图的方法。。。。。。 代码: #include <iostream>#include

poj 3255 次短路(第k短路) A* + spfa 或 dijkstra

题意: 给一张无向图,求从1到n的次短路。 解析: A* + spfa 或者 dijkstra。 详解见上一题:http://blog.csdn.net/u013508213/article/details/46400189 本题,spfa中,stack超时,queue的效率最高,priority_queue次之。 代码: #include <iostream>#i

poj 2449 第k短路 A* + spfa

poj 2449: 题意: 给一张有向图,求第k短路。 解析: A* + spfa。 一下转自:http://blog.csdn.net/mbxc816/article/details/7197228 “描述一下怎样用启发式搜索来解决K短路。 首先我们知道A*的基础公式:f(x)=g(x)+h(x);对h(x)进行设计,根据定义h(x)为当前的x点到目标点t所需要的实际距

【AcWing】852. spfa判断负环

#include<iostream>#include<algorithm>#include<cstring>#include<queue>using namespace std;const int N= 1e5+10;int n,m;int h[N],w[N],e[N],ne[N],idx;int dist[N],cnt[N];//cnt存最短路径的边数bool st[N];v

透析SPFA算法(图例讲解)

SPFA算法是Bellman-Ford的队列优化,所以先介绍Bellman-Ford算法。        Dijkstra算法是处理单源最短路径的有效算法,但它局限于边的权值非负的情况,若图中出现权值为负的边,Dijkstra算法就会失效,求出的最短路径就可能是错的。这时候,就需要使用其他的算法来求解最短路径,Bellman-

spfa+多重约束

普通的spfa只是用来求单源最短路(也就是边权和最小),是通过不断松弛边权来求的。 但是在一些情况需要求点权和最大或最小的情况(或者是其他的约束条件) 我们只需要根据条件加几个约束条件就行 以下是例题: L2-001. 紧急救援 时间限制:200 ms 内存限制:65536 kB 代码长度限制:8000 B 作为一个城市的应急救援队伍的负责人,

【HDU】1317 XYZZY spfa判负环+floyd求传递闭包

传送门:【HDU】1317 XYZZY 题目分析:首先我们可以用spfa判最长路上是否有正权环,但是有正权环却不等价于能到达终点。这是我们还需要判断是否能从正权环中走到终点,这个可以用传递闭包搞定。如果没有正权环就看是否能从起点到终点就好了。 代码如下: #include <cstdio>#include <cstring>#include <algorithm>

Bellman_Ford变形求最长路+正权回路或spfa——POJ 1860

对应POJ题目:点击打开链接 Currency Exchange Time Limit: 1000MS Memory Limit: 30000KTotal Submissions: 20814 Accepted: 7451 Description Several currency exchange points are working in our city. L