本文共 1048 字，大约阅读时间需要 3 分钟。

题意：

给你一棵无向树，然后给你一个点K，q个查询，每个查询一个x一个y，问从x到y经过k的最短路径

题目链接：

其实这个就是一个单源最短路的问题，以k为单源点，求k到每个点的最短距离,d[i],然后，从x到y的最短路径就是d[x]+d[y]；

这个题目转化一下思维方式就行了

注意点：

这是一个无向树，在构造边的时候要注意，两个方向都要加上

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int MAXN=1e5+50;const long long INF=1e18;int n;int k,p;long long dis[MAXN];int vis[MAXN];struct Edge{ int from; int to; int cost; Edge(int a,int b,int c) { from=a; to=b; cost=c; }};vector
         
           edges;vector
          
            G[MAXN];void Init(){ for(int i=0; i<=n; i++) G[i].clear(); edges.clear();}struct Heap{ int d,u; Heap(int a,int b) { d=a,u=b; } bool operator<(Heap h)const { return d>h.d; }};void Dijkstra(int s){ priority_queue
           
             p; p.push(Heap(0,s)); for(int i=0; i<=n; i++) dis[i]=INF; dis[s]=0; memset(vis,0,sizeof(vis)); while(!p.empty()) { Heap h=p.top(); p.pop(); int u=h.u; if(vis[u]) continue; for(int i=0; i
            
             dis[u]+e.cost) { dis[e.to]=dis[u]+e.cost; p.push(Heap(dis[e.to],e.to)); } } }}int main(){ scanf("%d",&n); Init(); for(int i=0; i
            
           
          
         
        
       
      
     
    
   

转载地址：http://cygsi.baihongyu.com/