Idealpath 双向bfs输出颜色,邻接矩阵实现
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 #include <map> 6 #include <algorithm> 7 8 using namespace std; 9 10 const int maxn=10000; 11 const int inf=1000000; 12 int G[maxn][maxn]; 13 int d[maxn]; 14 int vis[maxn]; 15 queue<int> q; 16 map<int,int> ma; 17 int path[maxn]; 18 int m,n; 19 20 void init() 21 { 22 for(int i=0;i<m;i++) 23 { 24 int l1,l2,rgb; 25 cin>>l1>>l2>>rgb; 26 27 //cout<<l1<<" "<<l2<<endl; 28 29 G[l1][l2]=G[l2][l1]=rgb; 30 } 31 } 32 33 void bfs(int dst) 34 { 35 memset(d,inf,sizeof(d)); 36 37 q.push(dst); 38 vis[dst]=1; 39 d[dst]=0; 40 41 42 while(!q.empty()) 43 { 44 int node=q.front(); 45 q.pop(); 46 47 for(int i=1;i<=n;i++) 48 if(G[node][i]>0) 49 if(!vis[i]) 50 { 51 d[i]=d[node]+1; 52 53 q.push(i); 54 vis[i]=1; 55 } 56 } 57 58 } 59 60 61 void p_bfs(int dst) 62 { 63 memset(vis,0,sizeof(vis)); 64 65 q.push(1); 66 67 while(!q.empty()) 68 { 69 int node=q.front(); 70 q.pop(); 71 72 if(node==dst) break; 73 74 for(int i=1;i<=n;i++) 75 if(G[node][i]>0) 76 if(d[i]==d[node]-1) 77 { 78 int index=d[1]-d[node]; 79 if(path[index]==0) path[index]=G[node][i]; 80 else path[index]=min(path[index],G[node][i]); 81 82 q.push(i); 83 } 84 } 85 86 for(int i=0;i<d[1]-d[dst];i++) 87 i==0? printf("%d",path[i]):printf(" %d",path[i]); 88 89 } 90 91 92 int main() 93 { 94 95 cin>>n; 96 cin>>m; 97 98 //cout<<"m:"<<m<<" "<<"n:"<<n<<endl; 99 100 init(); 101 102 int j; 103 cin>>j; 104 105 bfs(j); 106 107 //printf("d1:%d d2:%d d3:%d d4:%d d5:%d ",d[1],d[2],d[3],d[4],d[5]); 108 109 //printf("G[5][2]=%d G[5][1]=%d G[4][1]=%d G[2][1]=%d G[2][3]=%d G[1][3]=%d ",G[5][2],G[5][1],G[4][1],G[2][1],G[2][3],G[1][3]); 110 111 p_bfs(j); 112 113 114 printf(" "); 115 116 return 0; 117 }
邻接表实现最短距离
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 #include <vector> 6 #include <algorithm> 7 8 using namespace std; 9 10 const int maxn=100000+10; 11 const int inf=1000000; 12 vector<int> v; 13 int d[maxn]; 14 int vis[maxn]; 15 queue<int> q; 16 vector<int> G[maxn]; 17 int m,n; 18 19 void init() 20 { 21 for(int i=1;i<=n;i++) 22 G[i].clear(); 23 24 for(int i=0;i<m;i++) 25 { 26 int l1,l2; 27 cin>>l1>>l2; 28 29 //cout<<l1<<" "<<l2<<endl; 30 31 G[l1].push_back(l2); 32 G[l2].push_back(l1); 33 } 34 35 for(int i=1;i<=n;i++) 36 cout<<G[i].size()<<" "; 37 38 cout<<endl; 39 } 40 41 void bfs(int dst) 42 { 43 memset(d,inf,sizeof(d)); 44 45 q.push(dst); 46 vis[dst]=1; 47 d[dst]=0; 48 49 50 while(!q.empty()) 51 { 52 int node=q.front(); 53 q.pop(); 54 55 for(int i=0;i<G[node].size();i++) 56 if(!vis[G[node][i]]) 57 { 58 d[G[node][i]]=d[node]+1; 59 60 q.push(G[node][i]); 61 vis[G[node][i]]=1; 62 } 63 } 64 65 } 66 67 68 void p_bfs(int dst) 69 { 70 memset(vis,0,sizeof(vis)); 71 72 q.push(1); 73 74 printf("1"); 75 while(!q.empty()) 76 { 77 int node=q.front(); 78 q.pop(); 79 80 for(int i=0;i<G[node].size();i++) 81 if(d[G[node][i]]==d[node]-1) 82 { 83 printf(" %d",G[node][i]); 84 85 q.push(G[node][i]); 86 87 if(G[node][i]==dst) return; 88 89 break; 90 } 91 } 92 } 93 94 95 int main() 96 { 97 98 cin>>n; 99 cin>>m; 100 101 103 init(); 104 105 int j; 106 cin>>j; 107 108 bfs(j); 113 114 p_bfs(j); 115 116 117 printf(" "); 118 119 return 0; 120 }