蓝桥杯 算法训练 最短路 spfa

参考自：http://www.cnblogs.com/scau20110726/archive/2012/11/18/2776124.html

分成bfs与dfs两种思路

方法一：bfs

#include <iostream>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;  

#define MAX_N 20010
#define MAX_M 200010   
#define MAX 200000010
int head[MAX_N]; 
bool vis[MAX_N];   
int dis[MAX_N]; 
int n,m; 
struct node{
int v,value; 
int next; 
}edge[MAX_M];  

int cur=0; 

void add(int u,int v,int val){
node E={v,val,head[u]}; 
edge[cur]=E;
head[u]=cur++; 
}

void spfa(int x){ 
for (int i=1;i<=n;i++)
{
dis[i]=MAX; 
vis[i]=0; 
}
queue<int>q;     
q.push(x); 
vis[x]=1; 
dis[x]=0; 
while(!q.empty()){
int u=q.front(); 
q.pop();
vis[x]=0; 
for(int i=head[u];i!=-1;i=edge[i].next){
node E=edge[i]; 
if (dis[E.v]>dis[u]+E.value)  
{
dis[E.v]=dis[u]+E.value;  
if (!vis[E.v])
{
vis[E.v]=1; 
q.push(E.v);   
}

}
}
}
} 

int main(){ 

memset(head,-1,sizeof(head));  
cin>>n>>m; 
int u,v,val;  
for (int i=1;i<=m;i++)
{
cin>>u>>v>>val;    
add(u,v,val); 
} 
spfa(1); 
for(int i=2;i<=n;i++){
cout<<dis[i]<<endl; 
}
return 0;
}

方法二:dfs 

#include <iostream>
#include <cstring>
using namespace std;  

#define MAX_N 20010
#define MAX_M 200010   
#define MAX 200000010
int head[MAX_N];  
int dis[MAX_N]; 
struct node{
int v,value; 
int next; 
}edge[MAX_M];  

int cur=0; 

void add(int u,int v,int val){
node E={v,val,head[u]}; 
edge[cur]=E;
head[u]=cur++; 
}

void spfa_dfs(int u)
{
for(int k=head[u]; k!=-1; k=edge[k].next)
{
int v=edge[k].v,w=edge[k].value;  

if( dis[u]+w < dis[v] )
{  
dis[v]=dis[u]+w;
spfa_dfs(v); 
}
}
} 

int main(){ 
memset(head,-1,sizeof(head));   
int n,m;  
cin>>n>>m; 
for (int i=1;i<=n;i++)
{
dis[i]=MAX; 
}
dis[1]=0; 
int u,v,val;  
for (int i=1;i<=m;i++) 
{
cin>>u>>v>>val;    
add(u,v,val); 
} 
spfa_dfs(1); 
for(int i=2;i<=n;i++){
cout<<dis[i]<<endl; 
}
return 0;
}