HDU 6386 Age of Moyu(BFS求最短距离+DFS标记同值)

ERROR:具体过程其实与普通的BFS求最短路也没啥区别，就是需要一个数组（dis）来记录起点（1）到所有点的最短距离，然后每个点可以多次加入queue（用优先队列）。（这种方法已发现是有BUG的）

感谢@jianbagengmu给出样例

5 6
1 2 1
2 3 1
3 4 1
4 5 1
1 3 2
1 4 3
这种方法当遇到多条线路到达同一个点的花费相同但线路占领者不同时就会出问题。不过由于出题人可能没有考虑这种情况，导致这种错误方法也能AC。（事实上多校时我就是用这种方法过的。。。_(:з」∠)_）

bfs查询路径，每条边只走一次。每一个点入队列后，再用dfs把所有与当前边相同占领者的边的点加入。本质上是用dfs来压缩路径，然后bfs。因为按照普通的bfs找最短路径经验我们容易发现两个典型的性质

1：每次以当前点为中心加进来的相邻点的距离都为当前点距离+1。

2：必定为最短距离。

正确代码：

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 100005;
const int INF = 0x3f3f3f3f;
 
int N,M;
 
struct Edge{
    int to,id,next;//id是边的占领者 
    bool vis;
}E[MAXN*4];
 
int head[MAXN],tot;
queue<int> Q;
 
inline void Add(int from,int to,int id){
    E[++tot].next = head[from];
    E[tot].to = to;
    E[tot].id = id;
    E[tot].vis = false;
    head[from] = tot;
    E[++tot].next = head[to];
    E[tot].id = id;
    E[tot].to = from;
    E[tot].vis = false;
    head[to] = tot;
}
 
inline void init(){
    tot = 0;
    memset(head,0,sizeof head);
}
 
int dis[MAXN];//记录起点到所有点的最短距离
bool vis[MAXN];
 
void DFS(int x,int id,int num){
	if(!vis[x]){
		dis[x] = num;
		vis[x] = true;
		if(x == N)return;
		Q.push(x);
	}
	for(int i=head[x] ; i ; i=E[i].next){
		if(E[i].vis)continue;
		if(E[i].id == id){
			E[i].vis = true;
			DFS(E[i].to,id,num);
		}
	}
}
 
void BFS(int x){
	while(!Q.empty())Q.pop();
	memset(vis,false,sizeof vis);
	dis[x] = 0;
	dis[N] = -1;
	vis[x] = true;
	Q.push(x);
	while(!Q.empty()){
	    int t = Q.front();
	    Q.pop();
	    for(int i=head[t] ; i ; i=E[i].next){
	       if(E[i].vis)continue;
	       E[i].vis = true;
	       DFS(E[i].to,E[i].id,dis[t]+1);
	       if(dis[N] > 0)break;
	    }
	    if(dis[N] > 0)break;
	}
}
 
int main(){
    
    while(scanf("%d %d",&N,&M) == 2){
        init();
        if(M == 0){
            printf("-1\n");
            continue;
        }
        int a,b,c;
        for(int i=1 ; i<=M ; ++i){
            scanf("%d %d %d",&a,&b,&c);
            Add(a,b,c);
        }
        BFS(1);
        printf("%d\n",dis[N]);
    }
    
    return 0;
}