UVa 1599 Ideal Path【BFS】

题意：给出n个点，m条边，每条边上涂有一个颜色，求从节点1到节点n的最短路径，如果最短路径有多条，要求经过的边上的颜色的字典序最小

紫书的思路：第一次从终点bfs,求出各个节点到终点的最短距离，

第二次bfs从起点沿着每到达一个节点d[]减少1来走，按照颜色的字典序最小的路径来走

  1 #include<iostream>  
  2 #include<cstdio>  
  3 #include<cstring> 
  4 #include <cmath> 
  5 #include<stack>
  6 #include<vector>
  7 #include<map> 
  8 #include<set>
  9 #include<queue> 
 10 #include<algorithm>  
 11 using namespace std;
 12 
 13 typedef long long LL;
 14 const int INF = 1000000000;
 15 const int mod=1000000007;
 16 const int maxn=100005;
 17 
 18 struct Edge{
 19     int u,v,c;
 20     Edge(int u=0,int v=0,int c=0):u(u),v(v),c(c){}
 21 };
 22 
 23 vector<Edge> edges;
 24 vector<int> G[maxn];
 25 
 26 void addedges(int u,int v,int c){
 27     edges.push_back(Edge(u,v,c));
 28     int idx=edges.size()-1;
 29     G[u].push_back(idx);
 30 }
 31 
 32 int n,vis[maxn],d[maxn];
 33 
 34 void rev_bfs(){//求出每一个节点到终点n-1的距离 
 35     memset(vis,0,sizeof(vis));
 36     vis[n-1]=true;
 37     d[n-1]=0;
 38     
 39     queue<int> q;
 40     q.push(n-1);
 41     while(!q.empty()){
 42         int v=q.front();q.pop();
 43         for(int i=0;i<G[v].size();i++){
 44             int e=G[v][i];
 45             int u=edges[e].v;
 46             if(!vis[u]){
 47                 vis[u]=true;
 48                 d[u]=d[v]+1;
 49                 q.push(u);
 50             }
 51         }
 52     }
 53 }
 54 
 55 vector<int> ans;
 56 
 57 void bfs(){
 58     memset(vis,0,sizeof(vis));
 59     vis[0]=true;
 60     ans.clear();
 61     
 62     vector<int> next;
 63     next.push_back(0);
 64     
 65     for(int i=0;i<d[0];i++){
 66         int min_color=INF;
 67         for(int j=0;j<next.size();j++){
 68             int u=next[j];
 69             for(int k=0;k<G[u].size();k++){
 70                 int e=G[u][k];
 71                 int v=edges[e].v;
 72                 if(d[u]==d[v]+1)
 73                 min_color=min(min_color,edges[e].c); 
 74             }
 75         }
 76         
 77         ans.push_back(min_color);
 78                 
 79         vector<int> next2;
 80         for(int j=0;j<next.size();j++){
 81             int u=next[j];
 82             for(int k=0;k<G[u].size();k++){
 83                 int e=G[u][k];
 84                 int v=edges[e].v;
 85                 if(d[u]==d[v]+1&&edges[e].c==min_color&&!vis[v]) {
 86                     vis[v]=true;
 87                     next2.push_back(v);
 88                 }
 89             }
 90         }
 91         next=next2;        
 92     }
 93     
 94     printf("%d
",ans.size());
 95     printf("%d",ans[0]);
 96     for(int i=1;i<ans.size();i++) printf(" %d",ans[i]);
 97     printf("
");
 98 } 
 99 
100 int main(){
101     int m,u,v,c;
102     while(scanf("%d %d",&n,&m)==2){
103         edges.clear();
104         for(int i=0;i<n;i++) G[i].clear();
105         
106         while(m--){
107             scanf("%d %d %d",&u,&v,&c);
108             addedges(u-1,v-1,c);
109             addedges(v-1,u-1,c);
110         }
111         rev_bfs();
112         bfs();
113     }
114     return 0;
115 }

View Code

这道题放了一个月，最后还是看的标程，艾---看来有些题目不是拖得越久就会了，，，，

不要懒的说啊----

加油--gooooooooooooo---