时间限制: 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
基本上是裸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 }