简答题 偏难
#20402

上学 时间限制:1 s,内存限制:512 MB 【问题描述】 C 城可以视为由 n 个结点与 m 条边组成的无向图。这些结点依次以 1、2、……、n 标号,边依…

上学

时间限制:1 s,内存限制:512 MB

【问题描述】

C 城可以视为由 n 个结点与 m 条边组成的无向图。这些结点依次以 1、2、……、n 标号,边依次以 1、2、……、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  。

对于所有测试点,保证 1<=n<=2×10^5,1<=m<=2×10^5 ,1<=q<=2×10^5 ,1<=ui、vi、hi<=n ,1<=li<=10^6 。

保证给定的图联通。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; #include &lt;queue&gt; #include &lt;iostream&gt; using namespace std; const int N = 2e5 + 5; const int E = N &lt;&lt; 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 &lt;pair&lt;long long, int&gt;&gt; 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", &amp;n, &amp;m, &amp;s, &amp;q);     for (int i = 1; i &lt;= m; i++) {         int u, v, l;         scanf("%d%d%d", &amp;u, &amp;v, &amp;l);         ae(u, v, l);         ae(v, u, l);     }     for (int i = 1; i &lt;= 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] &lt; d[to[i]]) {                 d[to[i]] = d[u] + wt[i];                 pq.push({-d[to[i]], to[i]});             }     }     while (q--) {         int p;         scanf("%d", &amp;p);         printf("%lld\n", d[p]);     }     return 0; }</pre>
这道题暂未补解析。