Sicily-1024

攻城狮庆晨技术 2022年11月8日

0 收藏 438 点赞 1,271 浏览 1301 个字

一．题意：

有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 ;
 }