186. [USACO Oct08] 牧场旅行

★★ 输入文件：pwalk.in 输出文件：pwalk.out 简单对比
时间限制：1 s 内存限制：128 MB

n个被自然地编号为1..n奶牛（1<=n<=1000）正在同样被方便的编号为1..n的n个牧场中吃草。更加自然而方便的是，第i个奶牛就在第i个牧场中吃草。

其中的一些对牧场被总共的n-1条双向通道的一条连接。奶牛可以通过通道。第i条通道连接的两个牧场是A_i和B_i（1<=A_i<=N;1<=B_i<=N）其长度是L_i（1<=L_i<=10000）。

通道只会连接两个不同的牧场，所以这些通道使得整个牧场构成了一棵树。

奶牛们是好交际的希望能够经常的访问别的奶牛。急切地，它们希望你能通过告诉它们Q（1<=Q<=1000）对牧场的路径来帮助他们安排旅行。（这里将有Q个询问，p1,p2(1<=p1<=n；1<=p1<=n)）

分数：200

问题名称：pwalk

输入格式：

第1行：两个用空格隔开的整数：n和Q
第2..n行：第i+1行包含三个用空格隔开的整数：A_i,B_i和L_i
第n+1..N+Q行：每行包含两个用空格隔开的整数，代表两个不同的牧场，p1和p2

输入样例（file pwalk.in）：

输出格式：

第1..Q行：行i包含第i个询问的答案。

输出样例：

2
7

思路：spfa算法。

 1 #include<cstdio>
 2 #include<cstring>
 3 #define N 1010
 4 using namespace std;
 5 int n,q;
 6 int dis[N],map[N][N];
 7 bool vis[N];
 8 int que[N];
 9 int head,tail,d;
10 void spfa(int x)
11 {
12     memset(vis,0,sizeof(vis));
13     memset(dis,0x3f,sizeof(dis));
14     head=0;
15     tail=0;
16     que[tail++]=x;
17     vis[x]=1;
18     dis[x]=0;
19     while(head<tail)
20     {
21         d=que[head++];
22         vis[d]=0;
23         for(int i=1;i<=n;i++)
24             if(dis[i]>dis[d]+map[d][i])
25             {
26                 dis[i]=dis[d]+map[d][i];
27                 if(!vis[i])
28                 {
29                     que[tail++]=i;
30                     vis[i]=1;
31                 }
32             }
33     }
34 }
35 int main()
36 {
37     freopen("pwalk.in","r",stdin);
38     freopen("pwalk.out","w",stdout);
39     scanf("%d%d",&n,&q);
40     memset(map,0x7f,sizeof(map));
41     for(int i=1;i<n;i++)
42     {
43         int a,b,c;
44         scanf("%d%d%d",&a,&b,&c);
45         map[a][b]=map[b][a]=c;
46     }
47     for(int i=1;i<=q;i++)
48     {
49         int a,b;
50         scanf("%d%d",&a,&b);
51         spfa(a);
52         printf("%d
",dis[b]);
53     }
54     fclose(stdin);
55     fclose(stdout);
56     return 0;
57 }