自动搬运

查看原文

来自洛谷，原作者为

	laiyouming 这个家伙很懒，什么也没有留下

搬运于2025-08-24 23:11:44，当前版本为作者最后更新于2025-03-31 10:14:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

我们发现图是双向的。$x$ 到 $y$ 的距离等于 $y$ 到 $x$ 的距离。所以我们可以从学校进行一遍最短路。来统计答案。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,t,b[200001],d[200001],qd;
vector<pair<long long,long long>>a[200001];
set<pair<long long,long long>>c;
void dijkstra(){
	for(long long i=1;i<=n;i++){
		b[i]=1e18;
		c.insert({b[i],i});
	}
	c.erase({b[qd],qd});
	c.insert({0,qd});
	b[qd]=0;
	for(;!c.empty();){
		long long x=(*c.begin()).second;
		c.erase(c.begin());
		for(auto j:a[x]){
			if(b[x]+j.second<b[j.first]){
				c.erase({b[j.first],j.first});
				b[j.first]=b[x]+j.second,d[j.first]=x;
				c.insert({b[j.first],j.first});
			}
		}
	}
}
int main(){
	scanf("%lld%lld%lld%lld",&n,&m,&qd,&t);
	for(long long i=1;i<=m;i++){
		long long x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		a[x].push_back({y,z});
		a[y].push_back({x,z});
	}
	dijkstra();
	for(long long i=1;i<=t;i++){
		long long x;
		scanf("%lld",&x);
		printf("%lld\n",b[x]);
	}
}