Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 2359 | Accepted: 1157 |
Description
Given is an area in the far North comprising a number of villages and roads among them such that any village can be reached by road from any other village. Your job is to find the road distance between the two most remote villages in the area.
The area has up to 10,000 villages connected by road segments. The villages are numbered from 1.
Input
Output
Sample Input
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7
Sample Output
22 告诉我不是我一个人看到输入数据时不知道是什么意思
树的直径裸题
#include<stdio.h>
#include<string.h>
#include<queue>
#define MAX 40000
using namespace std;
int head[MAX];
int vis[MAX],dis[MAX];
int ans,sum,beg;
struct node
{
int u,v,w;
int next;
}edge[MAX];
void add(int u,int v,int w)
{
edge[ans].u=u;
edge[ans].v=v;
edge[ans].w=w;
edge[ans].next=head[u];
head[u]=ans++;
}
void bfs(int sx)
{
int i,j;
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
queue<int>q;
sum=0;
beg=sx;
q.push(sx);
while(!q.empty())
{
int top=q.front();
q.pop();
for(i=head[top];i!=-1;i=edge[i].next)
{
int x=edge[i].v;
if(!vis[x])
{ vis[x]=1;
dis[x]=dis[top]+edge[i].w;
q.push(x);
if(sum<dis[x])
{
sum=dis[x];
beg=x;
}
}
}
}
}
int main()
{
ans=0;
memset(head,-1,sizeof(head));
int a,b,c;
while(scanf("%d%d%d",&a,&b,&c)!=EOF)
{
add(a,b,c);
add(b,a,c);
}
bfs(1);
bfs(beg);
printf("%d\n",sum);
return 0;
}
poj 2631 Roads in the North【树的直径裸题】的更多相关文章
-
POJ 2631 Roads in the North(树的直径)
POJ 2631 Roads in the North(树的直径) http://poj.org/problem? id=2631 题意: 有一个树结构, 给你树的全部边(u,v,cost), 表示u ...
-
lightoj 1094 Farthest Nodes in a Tree 【树的直径 裸题】
1094 - Farthest Nodes in a Tree PDF (English) Statistics Forum Time Limit: 2 second(s) Memory Limit: ...
-
poj 2631 Roads in the North (*树的直径)
Roads in the North Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4513 Accepted: 215 ...
-
poj 2631 Roads in the North
题目连接 http://poj.org/problem?id=2631 Roads in the North Description Building and maintaining roads am ...
-
poj 1985 Cow Marathon【树的直径裸题】
Cow Marathon Time Limit: 2000MS Memory Limit: 30000K Total Submissions: 4185 Accepted: 2118 Case ...
-
POJ 2631 Roads in the North(求树的直径,两次遍历 or 树DP)
题目链接:http://poj.org/problem?id=2631 Description Building and maintaining roads among communities in ...
-
POJ 2631 Roads in the North (模板题)(树的直径)
<题目链接> 题目大意:求一颗带权树上任意两点的最远路径长度. 解题分析: 裸的树的直径,可由树形DP和DFS.BFS求解,下面介绍的是BFS解法. 在树上跑两遍BFS即可,第一遍BFS以 ...
-
POJ 2631 Roads in the North (树的直径)
题意: 给定一棵树, 求树的直径. 分析: 两种方法: 1.两次bfs, 第一次求出最远的点, 第二次求该点的最远距离就是直径. 2.同hdu2196的第一次dfs, 求出每个节点到子树的最长距离和次 ...
-
【POJ2631】Roads in the North 树的直径
题目大意:给定一棵 N 个节点的边权无根树,求树的直径. 代码如下 #include <cstdio> #include <algorithm> using namespace ...
随机推荐
-
UITextView 开始编辑时,文字没有左上角对齐解决办法 tableview整体上移
现实情况如上所示 我出现这种情况的原因有两种: 其一:没有给textview对齐方式: 其二:没有将BOOL类型的“ automaticallyAdjustsScrollViewInsets ”属性置 ...
-
selenium定位元素(本内容从https://my.oschina.net/flashsword/blog/147334处转载)
注明:本内容从https://my.oschina.net/flashsword/blog/147334处转载. 在使用selenium webdriver进行元素定位时,通常使用findElemen ...
-
64位系统如何导入excel
1.运行C:\Windows\SysWOW64\odbcad32.exe,打开后如下图所示: 2.点击添加,选择如下图所示Microsoft Excel Driver(*.xls) 3.点击完成,在弹 ...
- 优化MySchool数据库总结
-
【iOS】Quartz2D简单介绍
一.什么是Quartz2D Quartz 2D是⼀个二维绘图引擎,同时支持iOS和Mac系统 Quartz 2D能完成的工作: 绘制图形 : 线条\三角形\矩形\圆\弧等 绘制文字 绘制\生成图片(图 ...
-
基于CentOS与VmwareStation10搭建Oracle11G RAC 64集群环境:4.安装Oracle RAC FAQ-4.6.重新配置与缷载11R2 Grid Infrastructure
1.[root@linuxrac1 ~]# /u01/app/oraInventory/orainstRoot.sh 2.[root@linuxrac2 ~]# /u01/app/oraInvento ...
-
Scala控制语句
2019-04-16 19:03:01 if else 表达式 var sumVal = 0 if ( sumVal == 0 ) { println("true") } else ...
-
厉害了WORD大S
REPORT YLYTEST01. ) TYPE C VALUE 'ABC'. WRITE LV_C TO LV_C RIGHT-JUSTIFIED. '. WRITE LV_C. 结果: 另外收藏一 ...
-
MySQL存储引擎之Spider内核深度解析
作者介绍 朱阅岸,中国人民大学博士,现供职于腾讯云数据库团队.研究方向主要为数据库系统理论与实现.新硬件平台下的数据库系统以及TP+AP型混合系统. Spider是为MySQL/MariaDB开发 ...
-
Jedis API 详细示例
Jedis API 详细示例 https://www.jianshu.com/p/125357ee7651