1 条题解
-
0CDQZxuyifeng LV 9 @ 2017-09-08 16:28:10
//--------------------------------------------AC code--------------------------------------------//
#include<cstdio> #include<cstring> using namespace std; typedef long long LL; const int MAXN = 2005; int n, u, v, p, mark; LL ans = 1e15, res; struct Edge{ int nxt, to, dis; }edge[MAXN<<1]; int head[MAXN], edge_num; void add_edge(int from, int to, int dis){ edge[++edge_num].nxt = head[from]; edge[edge_num].to = to; edge[edge_num].dis = dis; head[from] = edge_num; } bool vis[MAXN]; void dfs(int x, int f, LL d, int no){ vis[x] = 1; if(d > res){ res = d; mark = x; } for(int i = head[x]; i; i = edge[i].nxt){ if(i == no || i == no+1 || edge[i].to == f || vis[edge[i].to]) continue; dfs(edge[i].to, x, d+1ll*edge[i].dis, no); } } int main(){ // freopen("foodshop.in", "r", stdin); // freopen("foodshop.out", "w", stdout); scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%d%d%d", &u, &v, &p); add_edge(u, v, p); add_edge(v, u, p); } for(int i = 1; i <= edge_num; i+=2){ bool f = true; memset(vis, 0, sizeof vis); res = mark = 0; dfs(1, 0, 0, i); for(int j = 1; j <= n; j++) if(!vis[j]){ f = false; break; } if(!f) continue; memset(vis, 0, sizeof vis); res = 0; dfs(mark, 0, 0, i); if(ans > res) ans = res; } printf("%.1lf", (double)ans * 0.5); return 0; }
- 1
信息
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 7
- 已通过
- 2
- 通过率
- 29%
- 上传者