codevs 1664 清凉冷水

1664 清凉冷水

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

     闷热的夏天,威斯康辛州的奶制品地区提供冷水供奶牛饮用,以此来解渴。农夫约翰将冷水通过N (3 <= N <= 99999; N 为奇数)个冷水管道,分别编号序号1..N从泵的位置一直送到牛棚里。当水在管道中流动时,夏天的热能使它变热。贝茜想要找到最冷的水,这样她就能比任何其他奶牛更好地享受这难得的好天气。

    她已经绘制了一整套完整的分支管道,并注意到这个管道系统犹如一棵树,它的根在农场,从根开始每个分支都分离出两个管道。令人惊讶的是,所有管道都有一个长度,当然这所有的N根管道连接成1条路或者和其他的管道路线连接。

    给出所有管道连接的地图,计算每一个分支点到牛棚的距离。贝茜将通过这些信息来找到最清凉冷水。

    管道的端点,可以作为分支点也可以作为管道终点,它以管道的编号命名。地图上包含C (1<= C <= N)个分支器,每个分支器包含3个数据,管道端点E_i (1<= E_i <= N),管道端点连接的两个管道B1_i, B2_i (2<= B1_i <=N; 2<= B2_i <=N)。管道1连接到牛棚,每两个连接器之间的管道长度均为1。

输入描述 Input Description

    * 第 1 行: 2个用空格隔开的整数 N , C

    * 第 2 至 C+1 行: 3个用空格隔开的整数,分别表示连接器的编号,以及连接的2个管道的编号E_i, B1_i, B2_i

输出描述 Output Description

     * 共 N 行: 分别表示每个管道到牛棚的最短距离。

样例输入 Sample Input

    5 2

    3 5 4

    1 2 3

样例输出 Sample Output

    1

    2

    2

    3

    3

数据范围及提示 Data Size & Hint

    +------+

    | Barn |

    +------+

    |  1

    *

    2 / \ 3

    *

       4 / \ 5

分类标签 Tags 点此展开

基本上是裸SPFA但是需要加一下数据处理

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 const int MAXN=100001;
 7 const int maxn=0x7fffffff;
 8 struct node
 9 {
10     int u;
11     int v;
12     int w;
13     int next;
14 }edge[MAXN];
15 int num=1;
16 int head[MAXN];
17 int dis[MAXN];
18 int vis[MAXN];
19 void spfa()
20 {
21     dis[1]=0;
22     vis[1]=0;
23     queue<int>q;
24     q.push(1);
25     while(q.size()!=0)
26     {
27         int p=q.front();
28         q.pop();
29         for(int i=head[p];i!=-1;i=edge[i].next)
30         {
31             int to=edge[i].v;
32             if(dis[to]>dis[p]+edge[i].w)
33             {
34                 dis[to]=dis[p]+edge[i].w;
35                 if(vis[to]==0)
36                 {
37                     vis[to]=1;
38                     q.push(to);
39                 }
40             }
41         }
42     }
43 }
44 int main()
45 {
46     int n,m;
47     scanf("%d%d",&n,&m);
48     for(int i=1;i<=n;i++)
49     {
50         head[i]=-1;
51         dis[i]=maxn;
52     }
53     for(int i=1;i<=m;i++)
54     {
55         int x,y,z;
56         scanf("%d%d%d",&x,&y,&z);
57         edge[num].u=x;
58         edge[num].v=y;
59         edge[num].w=1;
60         edge[num].next=head[x];
61         head[x]=num++;
62         edge[num].u=x;
63         edge[num].v=z;
64         edge[num].w=1;
65         edge[num].next=head[x];
66         head[x]=num++;
67     }
68     spfa();
69     for(int i=1;i<=n;i++)
70     {
71         printf("%d\n",dis[i]+1);
72     }
73     return 0;
74 }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏懒人开发

Eventbus3代码分析(五):getDefault(),register和EventBusBuilder等

除了注解,其他都和EventBus这个类有关系了 我们先从getDefault()方法开始分析

1202
来自专栏数据结构与算法

HUST 1017 - Exact cover

Time Limit: 15s Memory Limit: 128MB Special Judge Submissions: 7636 Solved: 38...

3327
来自专栏calmound

HDU 4609 3-idiots

http://acm.hdu.edu.cn/showproblem.php?pid=4609 题意:给你一组数,问可以组成多少个三角形 分析:才知道原来有FFT...

2916
来自专栏数据结构与算法

Educational Codeforces Round 42 (Rated for Div. 2)

942
来自专栏数据结构与算法

LOJ#2552. 「CTSC2018」假面(期望 背包)

转移的时候若要淦这个人,那么\(f[i][j] = (f[i - 1][j] + 1) * p + (f[i - 1][j]) * (1 - p)\)

1594
来自专栏数据结构与算法

2596 售货员的难题

2596 售货员的难题 时间限制: 1 s 空间限制: 32000 KB 题目等级 : 钻石 Diamond 题目描述 Description 某...

3586
来自专栏数据结构与算法

BZOJ1468: Tree

Description 给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K Input N(n<=40000) 接下来n-1行边描...

3269
来自专栏数据结构与算法

各种数论模板 不断更新 绝对精品

1.筛法求素数 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #inclu...

3489
来自专栏数据结构与算法

2017.5.13阶段模拟考试

预计分数:100+50(其实感觉自己写的对)+100 实际分数:100+0+100 P1149 火柴棒等式 题目描述 给你n根火柴棍,你可以拼出多少个形如“A+...

3536
来自专栏数据结构与算法

11.6NOIP模拟赛解题报告

很显然的一个贪心是从左往右扫,如果遇到一个不合法的点\(i\),那么升级\(i + R\)处的炮台。。

973

扫码关注云+社区

领取腾讯云代金券