请选择 进入手机版 | 继续访问电脑版

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

Description

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

Input

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

Output

第 1 行:能实现的购票请求数。
第 2 行:能实现的购票请求的最小总花费。

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%的数据,N<=100,M<=2,000。
对于 100%的数据,1<=N,M<=20,000,1<=K<=200,1<=Q<=50,000, 1<=d_i<=10,000。

Hint

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

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

代码:

const maxn=20001*3; maxv=20001; maxe=20001; type node=record y,next:longint; w:longint; end; var ls,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); begin inc(o); g[o].y:=y; g[o].w:=w; g[o].next:=ls[x]; ls[x]:=o; end; procedure spfa(first:longint;z:longint); var head,tail,t,i,x:longint; begin head:=0; tail:=1; list[1]:=first; for i:=1 to n do d[z,i]:=maxlongint; d[z,first]:=0; v[z,first]:=1; repeat head:=head+1; x:=list[head]; t:=ls[x]; while t>0 do with g[t] do begin if d[z,x]+w<d[z,y] then begin d[z,y]:=d[z,x]+w; if v[z,y]=0 then begin v[z,y]:=1; tail:=tail+1; list[tail]:=y; end; end; t:=next; end; v[z,x]:=0; until head>=tail; end; procedure check(c:longint); begin if c<>maxlongint then begin sum:=sum+1; ans:=ans+c; end; end; function min(x,y:longint):longint; begin if x<y then exit(x) else exit(y); end; procedure main; var i,j,x,y,w,t:longint; begin readln(n,m,k,q); for i:=1 to m do begin readln(x,y,w); add(x,y,w); end; for i:=1 to k do begin read(x); b[x]:=i; spfa(x,i); end; for i:=1 to q do begin read(x,y); if b[x]<>0 then check(d[b[x],y]) else begin q:=maxlongint; t:=ls[x]; while t>0 do begin if d[b[g[t].y],y]<>maxlongint then q:=min(q,d[b[g[t].y],y]+g[t].w); t:=g[t].next; end; check(q); end; end; writeln(sum); write(ans); end; begin main; end.

鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

粉丝0 阅读138 回复0
上一篇:
51Nod 1127 最短的包含字符串 (尺取法)发布时间:2018-01-07
下一篇:
Java---变量名、数据类型、输出语句发布时间:2018-01-07

精彩阅读

推荐视频

阅读排行榜

专访

关注官方微信

微信号:##

微博:##

QQ1群:653616923

QQ2群:536342758

服务QQ:

769993795

(工作日:周一至周五 9:00-16:00)
#

Archiver-手机版-小黑屋-站长统计-sitemap-sitemap- 蓝盘网

Powered by Discuz! X3.4© 2017-2018 Comsenz Inc.  豫ICP备17005739号-3