★★ 输入文件: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
输入格式:
输入样例(file pwalk.in):
4 2
2 1 2
4 3 2
1 4 3
1 2
3 2
输出格式:
输出样例:
2
7
输出说明:
询问1:牧场1和牧场2的路径长度为2。 询问2:3->4->1->2;总长为7。
思路:裸SPFA
错误原因:以后数组再开炸了吃屎!!!!!!!!!!!!!!!!!
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<queue>
6 using namespace std;
7 const int MAXN=1001;
8 const int maxn=0x7fffffff;
9 struct node
10 {
11 int u;
12 int v;
13 int w;
14 int next;
15 }edge[MAXN];
16 int num=1;
17 int head[MAXN];
18 int dis[MAXN];
19 int n,q;
20 int vis[MAXN];
21 int spfa(int bg,int ed)
22 {
23 for(int i=1;i<=n;i++)dis[i]=maxn;
24 memset(vis,0,sizeof(vis));
25 queue<int>q;
26 q.push(bg);
27 dis[bg]=0;
28 vis[bg]=1;
29 while(q.size()!=0)
30 {
31 int p=q.front();
32 q.pop();
33 for(int i=head[p];i!=-1;i=edge[i].next)
34 {
35 int to=edge[i].v;
36 if(dis[to]>dis[p]+edge[i].w)
37 {
38 dis[to]=dis[p]+edge[i].w;
39 if(vis[to]==0)
40 {
41 q.push(to);
42 vis[to]=1;
43 }
44 }
45 }
46 }
47 return dis[ed];
48 }
49 int main()
50 {
51 freopen("pwalk.in","r",stdin);
52 freopen("pwalk.out","w",stdout);
53 scanf("%d%d",&n,&q);
54 for(int i=1;i<=n;i++)head[i]=-1;
55 for(int i=1;i<n;i++)
56 {
57 scanf("%d%d%d",&edge[num].u,&edge[num].v,&edge[num].w);
58 edge[num].next=head[edge[num].u];
59 head[edge[num].u]=num++;
60 edge[num].v=edge[num-1].u;
61 edge[num].u=edge[num-1].v;
62 edge[num].w=edge[num-1].w;
63 edge[num].next=head[edge[num].u];
64 head[edge[num].u]=num++;
65 }
66 for(int i=1;i<=q;i++)
67 {
68 int bg;
69 int ed;
70 scanf("%d%d",&bg,&ed);
71 printf("%d\n",spfa(bg,ed));
72 }
73 return 0;
74 }