一. 题意:

有n个节点,n-1条边,并且任意两个节点都连通。模拟一下,实际上是一棵树的便利,求从特定根节点出发最长路径的值。这里用了广搜。

二. 每个节点只有两条邻接边,每个节点用一个vector来存储这些边。还有isVisited数组保证一条路径中一个节点只能经过一次。

三.

 //
// main.cpp
// sicily-1024
//
// Created by ashley on 14-10-13.
// Copyright (c) 2014年 ashley. All rights reserved.
// #include <iostream>
#include <vector>
using namespace std;
typedef struct
{
int left;
int right;
int weight;
}edge;
vector<edge> route;
vector<edge> adj[];
bool isVisited[];
void breadthSearch(int source, int &length, int pathLength)
{
isVisited[source] = true;
for (int i = ; i < (int)adj[source].size(); i++) {
if (isVisited[adj[source][i].right] == false || isVisited[adj[source][i].left] == false) {
if (pathLength + adj[source][i].weight > length) {
length = pathLength + adj[source][i].weight;
}
if (isVisited[adj[source][i].right] == false) {
breadthSearch(adj[source][i].right, length, pathLength + adj[source][i].weight);
}
if (isVisited[adj[source][i].left] == false) {
breadthSearch(adj[source][i].left, length, pathLength + adj[source][i].weight);
}
}
}
}
int main(int argc, const char * argv[])
{
int nodeNum, capital;
while (cin >> nodeNum >> capital) {
for (int i = ; i < ; i++) {
adj[i].clear();
isVisited[i] = false;
}
//memset(adj, 0, sizeof(adj));
//memset(isVisited, 0, sizeof(isVisited));
int l, r, w;
for (int i = ; i < nodeNum - ; i++) {
cin >> l >> r >> w;
adj[l].push_back(edge{l, r, w});
adj[r].push_back(edge{l, r, w});
}
int longest = ;
breadthSearch(capital, longest, );
cout << longest << endl;
}
return ;
}

源代码

最新文章

  1. Cookie的Secure属性
  2. Python2.6下基于rsa的加密解密
  3. GridView联表搜索,排序
  4. hdu1151 二分图(无回路有向图)的最小路径覆盖 Air Raid
  5. Oracle获取AWR和ASH
  6. Package &#39;DXCore for Visual Studio&#39; has failed to load properly
  7. 李洪强漫谈iOS开发[C语言-016]-变量的作用域
  8. input checkbox问题和li里面包含checkbox
  9. javascript 单行向上滚动文字
  10. C#反射(二) 【转】
  11. The fundamental knowledge of Node JS.
  12. BZOJ 1455: 罗马游戏( 配对堆 + 并查集 )
  13. 集群/分布式环境下5种session处理策略
  14. Query DSL(2)----Full text queries
  15. eclipse无法识别Web项目的问题
  16. python操作三大主流数据库(5)python操作mysql⑤使用Jinja2模板提取优化页面展示
  17. Latex数学公式中的空格
  18. vue 项目其他规范
  19. PHP 使用PHPExcel删除Excel单元格指定列
  20. 通过Spring Session实现新一代的Session管理

热门文章

  1. linux c 通过文件描写叙述符获取文件名称
  2. ASP.NET -- repeater控件的使用
  3. 关于两次指针(struct型)传参数的问题
  4. NOIP2010提高组] CODEVS 1069 关押罪犯(并查集)
  5. eclipse maven SLF4J: Failed to load class org.slf4j.impl.StaticLoggerBinder
  6. java代理课程测试 spring AOP代理简单测试
  7. 什么是weblogic?安装步骤详解
  8. 8,SSO,,eager copy,COW
  9. npm常用命令详解
  10. Qt之美(一):d指针/p指针详解