HDU

原题链接：HDU - 6386

题意： 

给你n个站点，m条边连接。每一条边都有一个编号，顺着编号相同的一直走整条路上只花费为1。如果在中途换到不同编号的边，则花费会增加。

思路：

或许一开始会想到最短路，我们先建个图然后用dijkstra跑一下。建图的话我们可能想到dfs或者bfs去搜索，相同编号则花费为1。然后....我们就TLE了

关于TLE主要是建图上我们单纯dfs或者bfs去搜索建图把新图中所有边权值求出来很费时间。 我们可以换一个思路，从最简单的搜索思路开始。

比如迷宫问题，我们一般可以用bfs找到最短的路径。 对于一个很长的路， a - c - d - e （走了四次，但是由于编号相同费用只花了1，那么我们可以用dfs来压缩一下路径。即我们dfs到 e了，说明 a-e 路径被压到了1。 所以我们在边bfs 边用 dfs压缩路径，最后就将其变为了最简单的迷宫最短路径问题。

code:

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0);
using namespace std;
const int maxn = 1e5+5;
int dist[maxn];
int head[maxn];
int vis[maxn];
int top;
int n,m;

struct Edge
{
    int v,vis,next;
    int color;
}edge[maxn<<2];
queue<int>Q;
void add(int u,int v,int color)
{
    edge[top].v = v;
    edge[top].next = head[u];
    edge[top].color = color;
    edge[top].vis = 0;
    head[u] = top++;

    edge[top].v = u;
    edge[top].next = head[v];
    edge[top].color = color;
    edge[top].vis = 0;
    head[v] = top++;
}
void dfs(int u,int color,int dis)
{
    if(!vis[u])
    {
        vis[u] = 1;
        dist[u] = dis;
        if(u==n) return;
        Q.push(u);
    }
    
    for(int i=head[u]; ~i ; i = edge[i].next)
    {
        if(edge[i].vis) continue;
        if(edge[i].color == color)
        {
            edge[i].vis = 1;
            dfs(edge[i].v,color,dis);
        }
        
    }
    
}
void bfs(int s)
{
    memset(vis,0,sizeof(vis));
    dist[s] = 0;
    dist[n] = -1;
    vis[s] = 1;
    while(!Q.empty()) Q.pop();
    Q.push(s);
    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        for(int i=head[u]; ~i ; i = edge[i].next)
        {
            if(edge[i].vis) continue;
            edge[i].vis = 1;
            dfs(edge[i].v,edge[i].color,dist[u]+1);
            if(dist[n]>0) return;
            
        }
    }
    return ;
}
void init()
{

    memset(dist,0,sizeof(dist));
    memset(head,-1,sizeof(head));
    top = 0;
}
int main()
{
    IOS
    while(cin>>n>>m)
    {
        init();
        if(!m)
        {
            printf("-1
"); 
            continue;
        }
        
        for(int i=0;i<m;i++)
        {
            int u,v,color;
            cin>>u>>v>>color;
            add(u,v,color);
        }
        bfs(1);
        printf("%d
",dist[n]);
    
    }
    return 0;
}