WA20求调
查看原帖
WA20求调
1421162
FeatQ楼主2025/6/21 01:47

代码如下 思路: 以学校为起点,跑一遍Dijkstra,然后反向累加每个dis[学生所在编号] 即可

#include <bits/stdc++.h>
using namespace std;
const int ml = 2e5 + 10;
struct node{
	int to,w;
};
vector<node> G[ml];
int vis[ml],dis[ml];
int n,m,s,q;
void dji(int x){
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	dis[x] = 0;
	set<pair<int,int>> st;
	st.insert(make_pair(dis[x],x));
	while(!st.empty()){
		auto now = *st.begin();
		st.erase(now);
		int u = now.second;
		if(vis[u] == 1) continue;
		vis[u] = 1;
		for(auto it : G[u]){
			int v = it.to;
			int w = it.w;
			if(dis[v] > dis[u] + w){
				dis[v] = dis[u] + w;
				st.insert(make_pair(dis[v],v));
			}
		} 
	}
}
int main (){
	cin >> n >> m >> s >> q;
	for(int i=1;i<=m;i++){
		int u,v,l;
		cin >> u >> v >> l;
		G[u].push_back({v,l});
		G[v].push_back({u,l});
	}
    dji(s);
	for(int i=1;i<=q;i++){
		int root;
		cin >> root;
		cout << dis[root] << endl;
	}
  return 0 ;
} 
2025/6/21 01:47
加载中...