代码如下 思路: 以学校为起点,跑一遍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 ;
}