给定一张n个点，m条边的带权有向无环图，同时给定起点S和终点T，一共有q个询问，每次询问删掉某个点和所有与它相连的边之后S到T的最短路，询问之间互相独立(即删除操作在询问结束之后会立即撤销)，如果删了那个点后不存在S到T的最短路，则输出-1。
输入描述:
第一行四个正整数表示n,m,S,T，意义如题所述；接下来m行每行三个正整数x[i],y[i],z[i]，表示有一条x[i]到y[i]的有向边，权值为z[i]；第m+1行一个正整数q表示询问次数；接下来q行每行一个正整数a[i]表示这次询问要删除点a[i]。n,q m z[i] = 10^9


输出描述:
q行每行一个数输出答案，如果删了这个点后不存在S到T的最短路，输出-1
示例1

输入

6 7 1 5
1 2 2
2 3 4
3 4 3
4 5 5
3 5 9
1 6 10
6 5 13
4
3
4
2
6

输出

23
15
23
14
加载中...