A28310. 上学
填空题
困难
知识点
题目描述
上学
题目描述
C 城可以视为由 n 个结点与 m 条边组成的无向图。这些结点依次以 1,2,3,,,,,n 标号，边依次以 1,2,3,,,,,m 标号。第i 条边（1≤ i ≤ m）连接编号为ui与vi的结点，长度为li米。
小 A 的学校坐落在 C 城中编号为 s 的结点。小 A 的同学们共有 q 位，他们想在保证不迟到的前提下，每天尽可能晚地出门上学。但同学们并不会计算从家需要多久才能到学校，于是找到了聪明的小 A。第 i 位同学（1≤ i ≤ q）告诉小 A，他的家位于编号为 hi 的结点，并且他每秒能行走 1 米。请你帮小 A 计算，每位同学从家出发需要多少秒才能到达学校呢？
输入格式
第一行，四个正整数 n,m,s,q，分别表示 C 城的结点数与边数，学校所在的结点编号，以及小 A 同学们的数量。
接下来 m 行，每行三个正整数 ui,vi,li，表示 C 城中的一条无向边。
接下来 q 行，每行一个正整数 hi，表示一位同学的情况。
输出格式
共 q 行，对于每位同学，输出一个整数，表示从家出发到学校的最短时间。
样例
输入样例 1
5 5 3 3
1 2 3
2 3 2
3 4 1
4 5 3
1 4 2
5
1
4输出样例 1
4
3
1数据范围
对于 20% 的测试点，保证 q=1。
对于另外 20% 的测试点，保证 1≤ n ≤ 500，1≤ m ≤ 500。
保证给定的图联通。
参考答案
#include <cstdio>
#include <queue>
#include <iostream>
using namespace std;
const int N = 2e5 + 5;
const int E = N << 1;
const long long oo = 1e18;
int n, m, s, q;
int h[N], to[E], nx[E], wt[E], et;
int vis[N];
long long d[N];
priority_queue <pair<long long, int>> pq;
void ae(int u, int v, int w) {
et++;
to[et] = v;
nx[et] = h[u];
wt[et] = w;
h[u] = et;
}
int main() {
scanf("%d%d%d%d", &n, &m, &s, &q);
for (int i = 1; i <= m; i++) {
int u, v, l;
scanf("%d%d%d", &u, &v, &l);
ae(u, v, l);
ae(v, u, l);
}
for (int i = 1; i <= n; i++)
d[i] = oo;
d[s] = 0;
pq.push( {
0, s
}
);
while (!pq.empty()) {
auto p = pq.top();
pq.pop();
int u = p.second;
if (vis[u])
continue;
vis[u] = 1;
for (int i = h[u]; i; i = nx[i])
if (d[u] + wt[i] < d[to[i]]) {
d[to[i]] = d[u] + wt[i];
pq.push( {
-d[to[i]], to[i]
}
);
}
}
while (q--) {
int p;
scanf("%d", &p);
printf("%lld\n", d[p]);
}
return 0;
}
上一题
下一题