[TIOJ] 1164. 喵喵的旅程
題目連結: http://tioj.infor.org/problems/1164 首先，不難發現本題要先找到鄉鎮最遠距離最小及最大的縣市，不過看起來這題限制滿死的，所以該怎麼做呢?這時就要想到C++內建的一個好用的函數minmax_element，於是就把他給的query塞進去，我們就找到了鄉鎮最遠距離最大及最小的縣市，取得後，就發現我們要找那兩個縣市的直徑(點與點之間最遠的距離)，那該怎麼找直徑呢?，就DFS兩次吧，先隨便從一個點開始DFS，找到最遠的那個點後，再從那個點DFS一遍，求出最大的距離即為該圖的直徑 #include "lib1164.h"
#include <bitset>
#include <utility>
#include <algorithm>
#include <vector>
using namespace std;
struct node{
int child,length;
};
vector<node> graph[1000001];
bitset<1000001> list(0);
pair<int,int> DFS(int which,int l){
int maxL=l,w=which,size=graph[which].size();
list[which]=1;
for(int i=0;i<size;i++){
int next = graph[which][i].child;
if (list[next]) continue;
pair<int,int> tt = DFS(next,l+graph[which][i].length);
if(tt.first>maxL){
maxL=tt.first;
w=tt.second;
}...