D - Age of Moyu HDU - 6386 -BFS+DFS分层最短路

• D - Age of Moyu

•  HDU - 6386 
• 题意：双向图，m条边，每条边有一个编号id，而花费就是根据这个id的变化来确定的求1-n的最短路
• 思路：全值为0,1的图直接bfs按层遍历图找到n就一定是最短，但是这里需要注意的是相连的边并且id是相同的
• 需要压缩成一个点，因为在这些边上走是一直花费为0的，所以bfs分层遍历同时进行着dfs路径压缩就可知得到最优解

• #include<bits/stdc++.h>
  using namespace std;
  const int maxn=100005;
  const int inf=0x3f3f3f3f;
  int n,m,head[maxn],w;
  int u,v,cnt,dis[maxn];
  bool vis[maxn];
  struct node
  {
      int v,id,to;
      bool flag;
  } edge[maxn*4];
  queue<int>q;
  void add(int u,int v,int id)
  {
      edge[++cnt].to=head[u];
      edge[cnt].v=v;
      edge[cnt].id=id;
      edge[cnt].flag=false;
      head[u]=cnt;
      edge[++cnt].id=id;
      edge[cnt].v=u;
      edge[cnt].to=head[v];
      edge[cnt].flag=false;
      head[v]=cnt;
  }
  void init()
  {
      cnt=0;
      memset(head,-1,sizeof(head));
  }
  void dfs(int x,int id,int num)
  {
      if(vis[x]==0)
      {
          dis[x]=num;
          vis[x]=1;
          if(x==n)return ;
          q.push(x);
      }
      for(int i=head[x]; i!=-1; i=edge[i].to)
      {
          if(edge[i].flag)continue;
          if(edge[i].id==id)
          {
              edge[i].flag=1;
              dfs(edge[i].v,id,num);
          }
      }
  }
  void bfs(int x)
  {
      while(!q.empty())q.pop();
      memset(vis,0,sizeof(vis));
      dis[x]=0;
      dis[n]=-1;
      vis[x]=1;
      q.push(x);
      while(!q.empty())
      {
          int top=q.front();
          q.pop();
          for(int i=head[top]; i!=-1; i=edge[i].to)
          {
              if(edge[i].flag)continue;
              edge[i].flag=1;
              dfs(edge[i].v,edge[i].id,dis[top]+1);
              if(dis[n]>0)return;
          }
      }
      return ;
  }
  int main()
  {
      while(~scanf("%d%d",&n,&m))
      {
          init();
          if(m==0)
          {
              printf("-1\n");
              continue;
          }
          while(m--)
          {
              scanf("%d %d %d",&u,&v,&w);
              add(u,v,w);
          }
          bfs(1);
          printf("%d\n",dis[n]);
      }
      return 0;
  }