【省选专题一】图论jzoj3936.【GDOI2015模拟11.22】假期计划spfa

Description

航空公司开设了连接着 N 个城市的航班。像任何航线一样&＃xff0c;这些城市中的 K 个被设为枢纽。
现在&＃xff0c;航空公司提供 M 个单行航班&＃xff0c;其中航班 i 从城市 u_i 到城市 v_i 并花 费 d_i 美元。像任何明智的航线一样&＃xff0c;对于每一个航班&＃xff0c;u_i 和 v_i 中至少一个是 枢纽。两个城市间最多有一个直飞航班&＃xff0c;并且没有航班起点与终点为同一城市。
小 X 负责为航空公司运营票务&＃xff0c;他收到了 Q 个学生假期的单行航班的请求&＃xff0c; 其中第 i 个请求是从城市 a_i 到另一个城市 b_i。
由于小 X 被处理这些票的工作淹没&＃xff0c;请帮他计算每个购票请求能否被实现&＃xff0c; 以及如果能实现时它的最小花费。
为了减小输出大小&＃xff0c;你只要输出可能的购票请求的总数&＃xff0c;以及它们总花费的 最小值。

Input

第 1 行&＃xff1a;N,M,K 和 Q。
第 2..1&＃43;M 行&＃xff1a;第 i&＃43;1 行包含 u_i,v_i 和 d_i。
第 2&＃43;M..1&＃43;M&＃43;K 行&＃xff1a;每行包含一个中枢的编号。
第 M&＃43;K&＃43;2..M&＃43;K&＃43;Q&＃43;1&＃xff1a;每行两个数&＃xff0c;表示从 a_i 到 b_i 的购票请求。

Output

第 1 行&＃xff1a;能实现的购票请求数。
第 2 行&＃xff1a;能实现的购票请求的最小总花费。

Sample Input

3 3 1 2
1 2 10
2 3 10
2 1 5
2
1 3
3 1

Sample Output

1
20

Data Constraint

对于 30%的数据&＃xff0c;N<&＃61;100&＃xff0c;M<&＃61;2,000。
对于 100%的数据&＃xff0c;1<&＃61;N,M<&＃61;20,000&＃xff0c;1<&＃61;K<&＃61;200&＃xff0c;1<&＃61;Q<&＃61;50,000&＃xff0c; 1<&＃61;d_i<&＃61;10,000。

Hint

对于第一个航班&＃xff0c;唯一可行的路线是 1->2->3&＃xff0c;花费 20。

分析&＃xff1a;一道水题。因为每条路有一个是枢纽&＃xff0c;且k<&＃61;200,从每个枢纽跑一遍spfa&＃xff0c;然后对于询问x&＃xff0c;y&＃xff0c;考虑x去到那个枢纽&＃xff0c;然后再加上该枢纽的到y最短路。

代码&＃xff1a;

constmaxn&＃61;20001*3;maxv&＃61;20001;maxe&＃61;20001;
typenode&＃61;recordy,next:longint;w:longint;end;varls,b:array [0..maxe] of longint;v,d:array [0..201,1..maxe] of longint;g:array [0..maxv] of node;list:array [0..maxn] of longint;n,m,k,q,sum,ans,o:longint;procedure add(x,y:longint; w:longint);begininc(o);g[o].y:&＃61;y; g[o].w:&＃61;w; g[o].next:&＃61;ls[x]; ls[x]:&＃61;o;end;procedure spfa(first:longint;z:longint);
varhead,tail,t,i,x:longint;
beginhead:&＃61;0; tail:&＃61;1;list[1]:&＃61;first;for i:&＃61;1 to n dod[z,i]:&＃61;maxlongint;d[z,first]:&＃61;0;v[z,first]:&＃61;1;repeathead:&＃61;head&＃43;1;x:&＃61;list[head];t:&＃61;ls[x];while t>0 dowith g[t] dobeginif d[z,x]&＃43;wthenbegind[z,y]:&＃61;d[z,x]&＃43;w;if v[z,y]&＃61;0 thenbeginv[z,y]:&＃61;1;tail:&＃61;tail&＃43;1;list[tail]:&＃61;y;end;end;t:&＃61;next;end;v[z,x]:&＃61;0;until head>&＃61;tail;
end;procedure check(c:longint);
beginif c<>maxlongint thenbeginsum:&＃61;sum&＃43;1;ans:&＃61;ans&＃43;c;end;
end;function min(x,y:longint):longint;beginif xthen exit(x)else exit(y);end;procedure main;var i,j,x,y,w,t:longint;
beginreadln(n,m,k,q);for i:&＃61;1 to m dobeginreadln(x,y,w);add(x,y,w);end;for i:&＃61;1 to k dobeginread(x);b[x]:&＃61;i;spfa(x,i);end;for i:&＃61;1 to q dobeginread(x,y);if b[x]<>0 then check(d[b[x],y])elsebeginq:&＃61;maxlongint;t:&＃61;ls[x];while t>0 dobeginif d[b[g[t].y],y]<>maxlongint thenq:&＃61;min(q,d[b[g[t].y],y]&＃43;g[t].w);t:&＃61;g[t].next;end;check(q);end;end;writeln(sum);write(ans);
end;beginmain;
end.