1463
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <math.h> #include <limits.h> using namespace std; // Datatypes typedef vector<int> vi; typedef vector<string> vs; typedef vector<vi> vvi; typedef pair<int,int> ii; typedef long long ll; typedef long double ld; // Define #define sz(a) int((a).size()) #define pb push_back #define all(c) (c).begin(),(c).end() #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define FOR(_i,_n) for(int (_i) = 0; (_i) < (_n); (_i)++) #define MP make_pair // Constants const double eps = 1e-8; const double PI = 3.1415926535897932384626433832795; #define INPUT_FILE "xo.in" #define OUTPUT_FILE "xo.out" int diam = 0; int diamv; vector< vector< pair<int,int> > > E; vector< int > color; vector< int > C; vector< int > m1v; vector< int > m2v; list<int> L; int dfs(int v) { color[v] = 1; if(E[v].size() == 0) { if(C[v] > diam) { diamv = v; diam = C[v]; } return C[v]; } else { int m1 = 0; int _m1v; int m2 = 0; int _m2v; int c = 0; for(int i = 0; i < E[v].size(); i++) { int u = E[v][i].first; if(color[u] == 0) { c++; int cc = E[v][i].second; int m = dfs(u) + cc; if(m > m1) { m2v[v] = m1v[v]; m1v[v] = u; m2 = m1; m1 = m; } else if (m > m2) { m2v[v] = u; m2 = m; } } } if(c > 1) { if(m1 + m2 + C[v] > diam) { diamv = v; diam = m1 + m2 + C[v]; } } if(m1 + C[v] > diam) { diamv = v; diam = m1 + C[v]; } return m1 + C[v]; } } void pr(int v) { while(v != 0) { L.pb(v); v = m1v[v]; } } void pr2(int v) { while(v != 0) { L.push_front(v); v = m1v[v]; } } int main(void) { #ifndef ALEX freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #else //freopen(INPUT_FILE, "r", stdin); //freopen(OUTPUT_FILE, "w", stdout); #endif int N,K; cin >> N >> K; C.resize(N+1); color.resize(N+1); E.resize(N+1); m1v.resize(N+1); m2v.resize(N+1); for(int i = 0; i < N; i++) { int t; scanf("%d", &t); C[i+1] = t; } for(int i = 0; i < K; i++) { int a,b,c; scanf("%d%d%d", &a, &b, &c); E[a].pb(MP(b,c)); E[b].pb(MP(a,c)); } for(int i = 1; i < N+1; i++) { if(color[i] == 0) dfs(i); } pr(diamv); pr2(m2v[diamv]); cout << diam << endl; cout << L.size() << endl; for(list<int>::iterator it = L.begin(); it != L.end(); it ++) { cout << *it << " "; } return 0; }
page revision: 0, last edited: 04 May 2008 14:41