专栏首页数据结构与算法186. [USACO Oct08] 牧场旅行

186. [USACO Oct08] 牧场旅行

157. [USACO Nov07] 奶牛跨栏

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 2
2 1 2
4 3 2
1 4 3
1 2
3 2

输出格式:

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

输出样例:

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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BZOJ 3714: [PA2014]Kuglarz(最小生成树)

    Description 魔术师的桌子上有n个杯子排成一行,编号为1,2,…,n,其中某些杯子底下藏有一个小球,如果你准确地猜出是哪些杯子,你就可以获得奖品。花...

    attack
  • 185. [USACO Oct08] 挖水井

    185. [USACO Oct08] 挖水井 ★★   输入文件:water.in   输出文件:water.out 简单对比 时间限制:1 s   内存限制:...

    attack
  • P2746 [USACO5.3]校园网Network of Schools

    题目描述 一些学校连入一个电脑网络。那些学校已订立了协议:每个学校都会给其它的一些学校分发软件(称作“接受学校”)。注意即使 B 在 A 学校的分发列表中, A...

    attack
  • BZOJ 3714: [PA2014]Kuglarz(最小生成树)

    Description 魔术师的桌子上有n个杯子排成一行,编号为1,2,…,n,其中某些杯子底下藏有一个小球,如果你准确地猜出是哪些杯子,你就可以获得奖品。花...

    attack
  • P1294 高手去散步

    题目背景 高手最近谈恋爱了。不过是单相思。“即使是单相思,也是完整的爱情”,高手从未放弃对它的追求。今天,这个阳光明媚的早晨,太阳从西边缓缓升起。于是它找到高手...

    attack
  • P1401 城市(30分,正解网络流)

    题目描述 N( )个城市,M( )条无向边,你要找T( )条从城市1到城市N的路,使得最长的边的长度最小,边不能重复用。 输入输出格式 输入格式: 第1行...

    attack
  • 185. [USACO Oct08] 挖水井

    185. [USACO Oct08] 挖水井 ★★   输入文件:water.in   输出文件:water.out 简单对比 时间限制:1 s   内存限制:...

    attack
  • NYOJ 32 组合数(dfs递归)

    Ch_Zaqdt
  • Dungeon Master POJ - 2251(bfs)

    _DIY
  • P2341 [HAOI2006]受欢迎的牛

    题目描述 每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶 牛都是自恋狂,每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——...

    attack

扫码关注云+社区

领取腾讯云代金券