186. [USACO Oct08] 牧场旅行

157. [USACO Nov07] 奶牛跨栏

186. [USACO Oct08] 牧场旅行,usacooct08

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):

4 22 1 24 3 21 4 31 23 2

输出格式:

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

输出样例:

27

输出说明:

询问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 node10 {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 }

 

 

157. [USACO Nov07] 奶牛跨栏

相关文章

Comment ()
评论是一种美德,说点什么吧,否则我会恨你的。。。