wa on #10
查看原帖
wa on #10
398152
MinimumSpanningTree最小生成树楼主2024/8/24 19:07
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
typedef pair<ll,int> PLI;
const int N=1e5+100;
const ll INF=1e10;
int n,u,v,w,k,t[N],q,m;
bool flag[N];
ll dis[N];
priority_queue<PLI,vector<PLI>,greater<PLI> > pq;
PLI qt;
struct node
{
	int id,last;
	ll val;
}a[N*2];
void add(int a1,int a2,int a3)
{
	a[++k].id=a2;
	a[k].last=t[a1];
	t[a1]=k;
	a[k].val=a3;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w),add(v,u,w);
	}
	for(int i=1;i<=n;i++) dis[i]=INF; 
	scanf("%d%d",&q,&m);
	dis[m]=0;
	pq.push({0ll,m});
	while(!pq.empty())
	{
		qt=pq.top(),pq.pop();
		if(flag[qt.second]) continue;
		flag[qt.second]=true;
		for(int i=t[qt.second];i;i=a[i].last)
		{
			//printf("%d %lld %d %lld\n",qt.second,qt.first,a[i].id,dis[a[i].id]);
			if(qt.first+a[i].val<dis[a[i].id])
			{
				dis[a[i].id]=qt.first+a[i].val;
				pq.push({dis[a[i].id],a[i].id});
				//printf("%d %lld\n",a[i].id,dis[a[i].id]);
			}
		}
	}
	//for(int i=1;i<=n;i++) printf("%d ",dis[i]);
	while(q--)
	{
		scanf("%d%d",&u,&v);
		printf("%lld\n",dis[u]+dis[v]);
	}
	return 0;
}
2024/8/24 19:07
加载中...