给了你n个村庄把，然后m条路径，q个询问，问你两个点之间的最短距离
分析：由于按照题意来说本图是没有环的，所以求a,b的最近公共祖先 到他们的各自的距离之和就是 那个他们的最短路啦，用的是tarjan来做的，我的方法定义了一个dis数组来随时记录路径的长度，其它大神各有自己的神奇之法
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define LL __int64 #define eps 1e-8 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector > G; //typedef pair P; //vector > ::iterator iter; // //map mp; //map ::iterator p; const int N = 10000 + 5; const int MAXN = 2000000 + 5; int pre[N]; int head[N],qhead[N]; int dis[N]; bool vis[N]; int tot,qtot; typedef struct Node { int from,nex,to; int lca; }; Node edge[N * 2],qedge[MAXN]; void clear() { memset(dis,0,sizeof(dis)); memset(vis,false,sizeof(vis)); memset(head,-1,sizeof(head)); memset(qhead,-1,sizeof(qhead)); for(int i=0;i<=N;i++) pre[i] = i; tot = qtot = 0; } void addedge(int u,int v,int w) { edge[tot].nex = head[u]; edge[tot].to = v; edge[tot].lca = w; head[u] = tot++; } void addqedge(int u,int v) { qedge[qtot].nex = qhead[u]; qedge[qtot].from = u; qedge[qtot].to = v; qedge[qtot].lca = -1; qhead[u] = qtot++; } int find(int x) { if(pre[x] != x)return find(pre[x]); return pre[x]; } void LCA(int u) { pre[u] = u; vis[u] = true; for(int i=head[u];i!=-1;i=edge[i].nex) { if(!vis[edge[i].to]) { dis[edge[i].to] = dis[u] + edge[i].lca; LCA(edge[i].to); pre[edge[i].to] = u; } } for(int i=qhead[u];i!=-1;i=qedge[i].nex) { if(vis[qedge[i].to]) { qedge[i].lca = dis[qedge[i].to] - dis[find(qedge[i].to)] + dis[u] - dis[find(qedge[i].to)]; qedge[i ^ 1].lca = qedge[i].lca; } } } int main() { int n,m,q; while(scanf("%d %d %d",&n,&m,&q) == 3) { clear(); while(m--) { int u,v,w; scanf("%d %d %d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } for(int i=0;i