2015: [Usaco2010 Feb]Chocolate Giving
2015: [Usaco2010 Feb]Chocolate Giving
HansBug
发布于 2018-04-10 17:02:06
发布于 2018-04-10 17:02:06
2015: [Usaco2010 Feb]Chocolate Giving
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 269 Solved: 183
Description
Farmer John有B头奶牛(1<=B<=25000)，有N(2*B<=N<=50000)个农场，编号1-N，有M(N-1<=M<=100000)条双向边，第i条边连接农场R_i和S_i(1<=R_i<=N;1<=S_i<=N)，该边的长度是L_i(1<=L_i<=2000)。居住在农场P_i的奶牛A(1<=P_i<=N)，它想送一份新年礼物给居住在农场Q_i(1<=Q_i<=N)的奶牛B，但是奶牛A必须先到FJ(居住在编号1的农场)那里取礼物，然后再送给奶牛B。你的任务是：奶牛A至少需要走多远的路程？
Input
第1行：三个整数：N,M,B。
第2..M+1行：每行三个整数：R_i,S_i和L_i，描述一条边的信息。
第M+2..M+B+1行：共B行，每行两个整数P_i和Q_i，表示住在P_i农场的奶牛送礼物给住在Q_i农场的奶牛。
Output
样例输出：
共B行，每行一个整数，表示住在P_i农场的奶牛送礼给住在Q_i农场的奶牛至少需要走的路程
Sample Input
6 7 3 1 2 3 5 4 3 3 1 1 6 1 9 3 4 2 1 4 4 3 2 2 2 4 5 1 3 6
Sample Output
6 6 10
HINT
Source
题解：继续领略SPFA的强大，就是这样——喵^_^
1 /**************************************************************
2 Problem: 2015
3 User: HansBug
4 Language: Pascal
5 Result: Accepted
6 Time:352 ms
7 Memory:5096 kb
8 ****************************************************************/
9
10 type
11 point=^node;
12 node=record
13 g,w:longint;
14 next:point;
15 end;
16 var
17 i,j,k,l,m,n,t:longint;
18 a:array[0..200000] of point;
19 b,c:array[0..200000] of longint;
20 procedure add(x,y,z:longint);inline;
21 var p:point;
22 begin
23 new(p);p^.g:=y;p^.w:=z;
24 p^.next:=a[x];a[x]:=p;
25 end;
26 procedure spfa(x:longint);inline;
27 var i,j,k,l,f,r:longint;p:point;
28 begin
29 b[1]:=x;f:=1;r:=2;
30 fillchar(c,sizeof(c),0);
31 c[x]:=1;
32 while f<r do
33 begin
34 p:=a[b[f]];
35 while p<>nil do
36 begin
37 if (c[p^.g]=0) or (c[p^.g]>(c[b[f]]+p^.w)) then
38 begin
39 c[p^.g]:=c[b[f]]+p^.w;
40 b[r]:=p^.g;
41 inc(r);
42 end;
43 p:=p^.next;
44 end;
45 inc(f);
46 end;
47 for i:=1 to n do dec(c[i]);
48 end;
49 begin
50 readln(n,m,t);
51 for i:=1 to n do a[i]:=nil;
52 for i:=1 to m do
53 begin
54 readln(j,k,l);
55 add(j,k,l);add(k,j,l);
56 end;
57 spfa(1);
58 for i:=1 to t do
59 begin
60 readln(j,k);
61 writeln(c[j]+c[k]);
62 end;
63 end. 本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-02-23 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录