UVA 1599 Ideal Path (HDU 3760)

两次bfs；

第一次bfs逆向搜索，得到每个点到终点的最短距离，找出最短路；第二次bfs根据最短距离可以选择满足条件的最短路。

注意！碰到这种很大数据量的题目一定要记得用scanf，printf 输入输出！！！

ps：uva和hdu中数据输入有些出入。。。（uva中没有输入T。。。）

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <queue>
  5 #include <algorithm>
  6 using namespace std;
  7 
  8 const int maxn=100000+10;
  9 const int inf=1000000000;
 10 
 11 struct node {
 12     int u,v,w;
 13     int next;
 14     void init (int nu,int nv,int nw,int nnext){
 15         u=nu;v=nv;w=nw;next=nnext;
 16     }
 17 }edges[maxn*4];
 18 
 19 int n,m,cnt;
 20 int head[maxn],d[maxn],visit[maxn];
 21 
 22 void addedges (int u,int v,int w){
 23     edges[cnt].init (u,v,w,head[u]);
 24     head[u]=cnt++;
 25 }
 26 
 27 void anti_bfs (){
 28     queue<int> q;
 29     while (!q.empty ())
 30         q.pop ();
 31     q.push (n);
 32     d[n]=0;
 33     while (!q.empty ()){
 34         int u=q.front ();
 35         q.pop ();
 36         for (int i=head[u];i!=-1;i=edges[i].next){
 37             int v=edges[i].v;
 38             if (d[v]==-1){
 39                 d[v]=d[u]+1;
 40                 q.push (v);
 41             }
 42         }
 43     }
 44     printf ("%d
",d[1]);//cout<<"error";
 45 }
 46 
 47 void bfs (){
 48     int p[maxn*2];
 49     int l,r;
 50     l=r=0;
 51     p[r++]=1;
 52     visit[1]=1;
 53     while (l<r){
 54         int mi=inf;
 55         for (int j=l;j<r;j++){
 56             int u=p[j];
 57             for (int i=head[u];i!=-1;i=edges[i].next){
 58                 int v=edges[i].v;
 59                 //if (visit[v]) continue ;
 60                 if (d[u]==d[v]+1)
 61                     mi=min (mi,edges[i].w);//cout<<edges[i].w<<"err"<<mi<<endl;
 62             }
 63         }
 64         printf ("%d",mi);
 65         int num=r;
 66         for (int j=l;j<r;j++){
 67             int u=p[j];
 68             for (int i=head[u];i!=-1;i=edges[i].next){
 69                 int v=edges[i].v;
 70                 if (visit[v]) continue ;
 71                 if (d[u]!=d[v]+1)
 72                     continue ;
 73                 if (mi==edges[i].w){
 74                     p[num++]=v;
 75                     visit[v]=1;//cout<<"error";
 76                     if (v==n){
 77                         printf ("
");
 78                         return ;
 79                     }
 80                 }
 81             }
 82         }
 83         printf (" ");
 84         l=r;
 85         r=num;
 86     }
 87 }
 88 
 89 int main (){
 90     int t;
 91     scanf ("%d",&t);
 92     while (t--){
 93         cnt=0;
 94         memset (head,-1,sizeof head);
 95         memset (d,-1,sizeof d);
 96         memset (visit,0,sizeof visit);
 97         scanf ("%d%d",&n,&m);
 98         for (int i=0;i<m;i++){
 99             int a,b,c;
100             scanf ("%d%d%d",&a,&b,&c);
101             addedges (a,b,c);
102             addedges (b,a,c);
103         }
104         anti_bfs ();
105         bfs ();
106     }
107     return 0;
108 }