# include <iostream>
# include <queue>
using
namespace
std
;
#define N 7
int
g[
7
][
7
] = { {
0
,
24
,
8
,
15
,-
1
,-
1
,-
1
}, {
24
,
0
,-
1
,-
1
,
6
,-
1
,
3
}, {
8
,-
1
,
0
,-
1
,
7
,
3
,-
1
}, {
15
,-
1
,-
1
,
0
,-
1
,-
1
,
4
}, {-
1
,
6
,
7
,-
1
,
0
,
2
,
9
}, {-
1
,-
1
,
3
,-
1
,
2
,
0
,
3
}, {-
1
,
3
,-
1
,
4
,
9
,
3
,
0
} };
int
dis[N]={
0
};
bool
is[N];
void
spaf(
int
w) {
memset
(is,
false
,
sizeof
(is));
memset
(dis,-
1
,
sizeof
(dis));
queue
<
int
>
queue
;
queue
.push(w); dis[w] =
0
; is[w] =
true
;
while
(!
queue
.empty()) {
int
x =
queue
.front(); is[x] =
false
;
queue
.pop();
for
(
int
i =
0
;i<N;i++) {
if
(g[x][i] != -
1
) {
if
(dis[i] == -
1
|| dis[x] + g[x][i] <dis[i]) { dis[i] = dis[x] + g[x][i];
if
(is[i] ==
false
) {
queue
.push(i); is[i] =
true
; } } } } } }
int
main() { spaf(
0
);
for
(
int
i =
0
;i<N;i++) {
printf
(
"%d "
,dis[i]); }
return
0
; }
最短路spaf算法
以hdu2544为例
#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
using
namespace
std
;
int
a[
123
][
123
],d[
123
];
bool
vis1[
123
][
123
],vis2[
123
];
void
init(){
memset
(vis1,
false
,
sizeof
(vis1));
memset
(vis2,
false
,
sizeof
(vis2));
for
(
int
i=
1
;i<=
123
;i++){
for
(
int
j=
1
;j<=
123
;j++){
if
(i==j) a[i][j]=
0
;
else
a[i][j]=
100
*
10000
; } }
for
(
int
i=
1
;i<=
123
;i++){ d[i]=
100
*
10000
; } }
int
main(){
int
n,m;
while
(
scanf
(
"%d %d"
,&n,&m),(n||m)){ init();
queue
<
int
>
que;
while
(!que.empty()) que.pop();
for
(
int
i=
1
;i<=m;i++){
int
u,v,w;
scanf
(
"%d %d %d"
,&u,&v,&w); a[u][v]=a[v][u]=w; vis1[u][v]=vis1[v][u]=
true
; } que.push(
1
); vis2[
1
]=
1
; d[
1
]=
0
;
while
(!que.empty()){
int
temp=que.front(); que.pop(); vis2[temp]=
0
;
for
(
int
i=
1
;i<=n;i++){
if
(vis1[temp][i]){
if
(d[i]>d[temp]+a[temp][i]){ d[i]=d[temp]+a[temp][i];
if
(!vis2[i]){ vis2[i]=
1
; que.push(i); } } } } }
printf
(
"%d\n"
,d[n]); }
return
0
; }
spaf算法解题
#include<iostream> #include<queue> using namespace std; int g[101][101]={0}; bool is[101] ; int dis[101]; void spaf(int n,int w) { queue<int> queue; queue.push(w); memset(is,false,sizeof(is)); memset(dis,-1,sizeof(dis)); dis[w] = 0; is[w] = true; while(!queue.empty()) { int x = queue.front(); is[x] = false; queue.pop(); for(int i =1;i<=n;i++) { if(g[x][i] != -1) { if(dis[i] == -1 || dis[x] + g[x][i] < dis[i]) { dis[i] = dis[x] + g[x][i]; if(is[i] == false) { is[i] = true; queue.push(i); } } } } } } int main() { int n,m,a,b,c; while(1) { memset(g,-1,sizeof(g)); scanf("%d %d",&n,&m); if(n == 0 && m == 0) { break; } for(int i = 1;i<=n;i++) { g[i][i] = 0; } for(int i =0;i<m;i++) { scanf("%d %d %d",&a,&b,&c); g[a][b] = c; g[b][a] = c; } spaf(n,1); printf("%d\n",dis ); } return 0; }
本文网址： http://www.appike.com/d/2021117105214_2471_2020208643/home