# 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