题解

1 条题解

  • 0
    @ 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%
上传者