機房

數組鏈式前向星建圖+堆優化版dijkstra

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
typedef pair<int,int> pii;
//無向圖開兩倍
int e[200005],ne[200005],v[200005],h[200005],du[100005],idx;
int dist[100005],st[100005];
vector<pair<int,int>> ve;
//利用數組鏈式前向星建圖
void add(int x,int y,int d)
{e[++idx]=y;ne[idx]=h[x];//v數組即把該點的度數轉為從該點出的邊的權值v[idx]=d;h[x]=idx;
}
void dijkstra(int x,int y)
{memset(st,0,sizeof(st));memset(dist,0x3f,sizeof(dist));dist[x]=0;//用最小堆優化priority_queue<pii,vector<pii>,greater<pii>> q;q.push({0,x});while(!q.empty()){int u=q.top().first,vv=q.top().second;q.pop();//即已經找到x到y的最小距離if(vv==y) return;//即該點已經被中轉過了if(st[vv]) continue;st[vv]=1;for(int i=h[vv];i!=0;i=ne[i]){int node=e[i];if(dist[node]>dist[vv]+v[i]){dist[node]=dist[vv]+v[i];q.push({dist[node],node});}}}
}
int main()
{int n,m;cin>>n>>m;for(int i=0;i<n-1;i++){int x,y;cin>>x>>y;ve.push_back({x,y});du[x]++;du[y]++;}for(int i=0;i<n-1;i++){int x=ve[i].first;int y=ve[i].second;add(x,y,du[x]);add(y,x,du[y]);}for(int i=0;i<m;i++){int u,v;cin>>u>>v;dijkstra(u,v);//最后要加上終點的權值cout<<dist[v]+du[v]<<endl;}return 0;
}