之前看到一题需要并查集+SPFA，然后就特别囧的发现自己SPFA这个历史遗留问题已经不知道怎么打了╮(╯▽╰)╭
就果断挑了一题特别裸的SPFA赶紧搞搞掉，顺便自己乱YY下学SPFA的笔记，免得自己下次又逗比了
SPFA是求最短路问题的一种解法
解决的是单源最短路，也就是求所有点到某一个点的最短路
反正自己乱YY当成是最短的路径+BFS+是否入队就完事了，大概的看程序的标注【QAQ...表示还好自己看得懂自己的程序】
据说调用STL的队列更省事，哪天学学嗯
【题目描述】情人节到了，情侣们也活跃起来了。这不，GoldenSun和Yoyo_Yao分到了同一个班上（真有缘）。这天，GoldenSun专门跑到了花店，为Yoyo_Yao选了999支玫瑰花（-_-|||），可当GoldenSun说了一大堆肉麻的话，正准备把花送给Yoyo_Yao时，班主任DuBowen进来了，无奈的GoldenSun只得从自己的位子上把花传给Yoyo_Yao。如果一整束传，不但比较抢眼，说不定还会被中途的一些八卦的人抢走，所以GoldenSun只能一支一支的传。已知GoldenSun他们班的座位是一个矩形，GoldenSun的位子在(x,m)，Yoyo_Yao的位子在(y,n)，传玫瑰时，只能纵横传而不能斜传（更不能扔）。又知GoldenSun班上的同学很八卦，每经过一个同学传时，玫瑰花就会扣去一定的成长值（玫瑰先开始有个成长值），即那个同学的八卦度，当玫瑰的成长值不大于0时，玫瑰就会凋零。GoldenSun希望自己的心血不要白费，即所有的玫瑰花都能传到Yoyo_Yao手中，所以如果有这种情况，GoldenSun就会自己冒着风险送这朵玫瑰。请你帮GoldenSun找到一条令玫瑰成长值为最高的路线，让GoldenSun能向Yoyo_Yao在情人节之际表达自己的爱意。【输入格式】输入第一行有2个用空格隔开的整数a和b，表示班里有a行b列（1<=a,b<=90）。第二行有四个用空格隔开的整数x,m,y,n，(x,m)为GoldenSun的座位，(y,n)为Yoyo_Yao的座位。（1<=x,y<=a;1<=m,n<=b） 第三行有一个整数love为单支玫瑰的最初成长值。(0<love<=maxlongint)来的a行是一个a*b的矩阵，矩阵中第i行j列的正整数表示坐在第i行j列的学生的八卦程度，每行的b个整数之间用空格隔开。（当然他们两个人的八卦程度为0）八卦程度(0<=bg<=love)【输出格式】输出共一行，包含一个整数，表示单支玫瑰最后成长值的最大值。如果是GoldenSun自己送，则输出love，即单支玫瑰的最初成长值。【输入样例】2 21 1 2 230 11 0【输出样例】2 |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 |
#include<cstdio>#include<cstring>using
namespace std;int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};int dis[100][100],n,m,t,d1[100000],d2[100000],a[100][100];bool
v[100][100];//标记是否入队☆void
spfa(int
x,int y){ int
h=1,w=1,i,xx,yy,c,b,j; memset(dis,20,sizeof(dis)); memset(v,true,sizeof(v)); d1[h]=x;d2[h]=y; dis[x][y]=0; v[x][y]=false; while(h<=w){//有点类似于BFS☆ int
b=d1[h],c=d2[h]; for(i=0;i<4;i++){ xx=b+dx[i]; yy=c+dy[i]; if(xx>0 && xx<=n && yy>0 && yy<=m){ if(dis[xx][yy]>dis[b][c]+a[xx][yy]){//☆ dis[xx][yy]=dis[b][c]+a[xx][yy]; if(v[xx][yy]){ w++; d1[w]=xx;d2[w]=yy; v[xx][yy]=false; }}}} v[b][c]=true; h++;}}int
main(){ int
i,j,s,x,y,xx,yy; freopen("sendrose.in","r",stdin);freopen("sendrose.out","w",stdout); scanf("%d%d%d%d%d%d%d",&n,&m,&x,&y,&xx,&yy,&t); for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&a[i][j]); spfa(x,y); if((t-dis[xx][yy])>=0 && t-dis[xx][yy]!=t) printf("%d",t-dis[xx][yy]); else
printf("%d",t); return
0;} |
原文：http://www.cnblogs.com/polebug/p/3682003.html