文档章节

sicily 1024 Magic Island

Ciel
 Ciel
发布于 2012/12/16 11:11
字数 417
阅读 158
收藏 0

Description

There are N cities and N-1 roads in Magic-Island. You can go from one city to any other. One road only connects two cities. One day, The king of magic-island want to visit the island from the capital. No road is visited twice. Do you know the longest distance the king can go.

Input

There are several test cases in the input
A test case starts with two numbers N and K. (1<=N<=10000, 1<=K<=N). The cities is denoted from 1 to N. K is the capital.

The next N-1 lines each contain three numbers XYD, meaning that there is a road between city-X and city-Y and the distance of the road is D. D is a positive integer which is not bigger than 1000.
Input will be ended by the end of file.

Output

One number per line for each test case, the longest distance the king can go.

Sample Input

3 1
1 2 10
1 3 20

Sample Output

20

分析:

本题要求指定起点到所有其他点的最长路径,需要遍历所有顶点,但不一定是所有的边,DFS更好些,然后直接套用DFS不断更新长度记录比较得出最大值即可。

代码:

// Problem#: 1024
// Submission#: 1788079
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

#define MAX 10010

struct node{
    int e,d;
    node( int a, int b ){
    e = a; d = b;
    }
};

vector<node> buffer[MAX];
bool visit[MAX];
int re;

void dfs( int v, int len ){
    if( len>re ) re = len;
    visit[v] = true;
    for( int i=0 ; i<buffer[v].size() ; i++ ){
    node temp = buffer[v][i];
    if( !visit[temp.e] ){
        visit[temp.e] = true;
        len += temp.d;
        dfs(temp.e,len);
        visit[temp.e] = false;
        len -= temp.d;
    }
    }
}

int main(){
    int n,k;
    int x,y,z;
    while( cin>>n ){
    cin >> k;
    for( int i=0 ; i<n-1 ; i++ ){
        cin >> x >> y >> z;
        buffer[x].push_back(node(y,z));
        buffer[y].push_back(node(x,z));
    }
    memset(visit,0,sizeof(visit));
    re = 0;
    dfs(k,0);
    cout << re << endl;
    for( int i=1 ; i<=n ; i++ )
        buffer[i].clear();
    }
    return 0;
}

© 著作权归作者所有

Ciel
粉丝 3
博文 24
码字总数 18532
作品 0
程序员
私信 提问
Oracle 11g R2 ADG 搭建

--============Oracle ADG搭建============== --==========准备阶段========= 1.检查primary为archivelog模式。 select log_mode from v$database; 如果为noarchivelog模式,切换到archivelo......

UltraSQL
2018/07/23
0
0
Head First C学习日志 第六章用堆进行动态存储

书中的例子是,在多座岛屿间规划航线,并记录,将岛屿作为节点,数据结构如下 typedef struct island { char *name; char *opens; char *closes; struct island *next;} island; 注意,递归结...

AlexTuan
2016/02/21
68
0
通过ramdisk内核模块研究Linux文件系统

在《深入Linux设备驱动程序内核机制》第11章"块设备驱动程序” 11.2节当中给出了ramdisk的两个版本的实现,这个示例的目的除了让读者直观感受一下编写一个块设备驱动程序的大体框架和关键元素...

nothingfinal
2012/02/22
0
0
FileChannel.transferTo for large file in windows

Using Java NIO use can copy file faster. I found two kind of method mainly over internet to do this job. public static void copyFile(File sourceFile, File destinationFile) throw......

pczhangtl
2014/03/30
204
0
[Leetcode] Max Area of Island 最大岛屿面积

Max Area of Island 最新更新请见:https://yanjia.me/zh/2019/02/... Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-di......

ethannnli
09/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

分页查询

一、配置 /*** @author beth* @data 2019-10-14 20:01*/@Configurationpublic class MybatisPlusConfig { @Bean public PaginationInterceptor paginationInterceptor(){ ......

一个yuanbeth
昨天
5
0
在LINQPad中使用Ignite.NET

LINQPad是进行.NET开发的一款优秀工具,非常有利于Ignite.NET API的快速入门。 入门 下载LINQPad:linqpad.net/Download.aspx,注意要选择64位操作系统的AnyCPU版本; 安装Ignite.NET的NuGet...

李玉珏
昨天
6
0
JS其他类型值转化为Boolean类型规则

本文转载于:专业的前端网站➤JS其他类型值转化为Boolean类型规则 由于最近在笔试的时候,发现好多关于其他类型转化为Boolean类型的题目,因此总结一下! 一、String类型转化为Boolean 1.转化...

前端老手
昨天
6
0
EurekaClient自动装配及启动流程解析

在上篇文章中,我们简单介绍了EurekaServer自动装配及启动流程解析,本篇文章则继续研究EurekaClient的相关代码 老规矩,先看spring.factories文件,其中引入了一个配置类EurekaDiscoveryClie...

Java学习录
昨天
10
0
析构函数是否必须为虚函数?为何?

p517 在C++中,基类指针可以指向一个派生类的对象。如果基类的析构函数不是虚函数,当需要delete这个指向派生类的基类指针时,就只会调用基类的析构函数,而派生类的析构函数无法被调用。容易...

天王盖地虎626
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部