時間限制 : 1 秒

內存限制 : 128 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行，對于每位同學，輸出一個整數，表示從家出發到學校的最短時間。

樣例

輸入

5 5 3 3
1 2 3
2 3 2
3 4 1
4 5 3
1 4 2
5
1
4

輸出

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,s,hi<=n ，1<=li<=10^6 。保證給定的圖聯通。

———————————————————————————————————————————思路：

以學校為原始的點，Dijkstra算法求學校到每一個點的時間。

代碼：

#include<bits/stdc++.h>
using namespace std;
const int N=200002;
int n,m,s,t,dis[N];
bool v[N];
struct node
{int v,e;
};
vector<node> q[N];
priority_queue<pair<int,int>>Q;
int main()
{scanf("%d%d%d%d",&n,&m,&s,&t);for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);q[a].push_back(node{c,b});q[b].push_back(node{c,a});}for(int i=1;i<=n;i++){dis[i]=INT_MAX;}dis[s]=0;memset(v,0,sizeof(v));while(!Q.empty()) Q.pop();Q.push(make_pair(0,s));while(!Q.empty()){int wz=Q.top().second;Q.pop();v[wz]=1;for(int i=0;i<q[wz].size();i++){if(dis[q[wz][i].e]>dis[wz]+q[wz][i].v){dis[q[wz][i].e]=dis[wz]+q[wz][i].v;if(!v[q[wz][i].e]){Q.push(make_pair(-dis[q[wz][i].e],q[wz][i].e));}}}}for(int i=1;i<=t;i++){int d;scanf("%d",&d);printf("%d\n",dis[d]);}return 0;
}