正确的写法是，在 dijkstra 过程中，若通过 $(u,v)$ 松弛了 $v$，则记录 $fa_v=id_{(u,v)}$ 表示最短路树上 $v$ 的连向祖先的边的编号。
但是如果将 $fa_v$ 记录为 $u$ 就 WA 50 pts。
请问原理是什么啊。 /fad

以下给出错误的写法：

inline void Dijkstra(){
	fill(dis,dis+n+1,+oo),vis.reset();
	dis[n]=0.0,q.push(node(n,dis[n]));
	while(q.size()){
		int u=q.top().u; q.pop();
		if(vis[u]) continue;
		vis[u]=1; gfore(u,R){
			int v=R.e[i].to; db w=R.e[i].w;
			if(dis[v]>dis[u]+w)
				dis[v]=dis[u]+w,fa[v]=u, //***here***
				q.push(node(v,dis[v]));
		}
	}
}

建立可并堆部分：

gfore(u,G){
	int v=G.e[i].to; db w=G.e[i].w;
	if(v==fa[u]) continue;
	root[u]=Mer(root[u],Cre(v,dis[v]-dis[u]+w));
} root[u]=Mer(root[u],root[fa[u]]);