hui

用户名：huih

访问量：4772

签　名：

等　　级
排　　名	248
经　　验	6040
参赛次数	2
文章发表	14
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2017年第八届真题-对局匹配- 过样例== ac ？？（C++代码）
浏览：171

最长不含重复字符的子字符串-题解（C++尺取法）
浏览：239

双向循环链表
浏览：104

你可能喜欢

蓝桥杯2013年第四届真题-大臣的旅费-题解（cpp迪杰斯特拉）

　　作者: hui　　　　发表时间：2020-07-21 15:53:57 浏览：428　|　评论：0　

原题链接：蓝桥杯2013年第四届真题-大臣的旅费

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 10011, M = 10011;
struct edge {
    int v, w, next;
    edge() {}
    edge(int a, int b, int c) { v = a, w = b, next = c; }
} e[M << 1];
struct node {
    int v, w;
    node(int a, int b) { v = a, w = b; }
    friend bool operator<(node a, node b) { return a.w > b.w; }
};
int vis[N], dis[N], head[N];
int len;
int pos, maxn = -1e9;
int n;
void init() {
    memset(vis, 0, sizeof vis);
    memset(dis, 0x3f, sizeof dis);
}
void add(int u, int v, int w) {
    e[len] = edge(v, w, head[u]);
    head[u] = len++;
}
void build(int u, int v, int w) {
    add(u, v, w);
    add(v, u, w);
}
void dj(int x) {
    priority_queue< node > q;
    q.push(node(x, 0));
    dis[x] = 0;
    while (q.size()) {
        node cur = q.top();
        q.pop();
        int u = cur.v;
        if (!vis[u])
            vis[u] = 1;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].v;
            int w = e[i].w;
            if (!vis[v] && dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push(node(v, dis[v]));
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (maxn < dis[i]) {
            maxn = dis[i];
            pos = i;
        }
    }
}
signed main() {
    memset(head, -1, sizeof head);
    len = 0;
    init();
    cin >> n;
    for (int i = 1, u, v, w; i < n; ++i) {
        cin >> u >> v >> w;
        build(u, v, w);
    }
    dj(1);
    init();
    dj(pos);
    int ans = 0;
    for (int i = 1; i <= maxn; ++i) {
        ans += i + 10;
    }
    cout << ans << '\n';
    return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

hui

TA的其他文章

你可能喜欢

C二级辅导-阶乘数列（C语言代码）

C二级辅导-进制转换（C++代码）

母牛的故事（C语言代码）

Hello, world! （C语言代码）

字符逆序（C语言代码）

蓝桥杯2013年第四届真题-大臣的旅费-题解（cpp迪杰斯特拉）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.7 （C++代码）

C二级辅导-同因查找（C语言代码）

C语言训练-求函数值（C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C++代码）

买不到的数目（C++代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

WU-整数平均值（C++代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

完数（C语言代码）

hui

TA的其他文章

你可能喜欢

C二级辅导-阶乘数列 （C语言代码）

C二级辅导-进制转换 （C++代码）

母牛的故事 （C语言代码）

Hello, world! （C语言代码）

字符逆序 （C语言代码）

蓝桥杯2013年第四届真题-大臣的旅费-题解（cpp迪杰斯特拉）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.7 （C++代码）

C二级辅导-同因查找 （C语言代码）

C语言训练-求函数值 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C++代码）

买不到的数目 （C++代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

WU-整数平均值 （C++代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

完数 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

C二级辅导-进制转换（C++代码）

母牛的故事（C语言代码）

字符逆序（C语言代码）

　　评论区

C二级辅导-同因查找（C语言代码）

C语言训练-求函数值（C语言代码）

买不到的数目（C++代码）

WU-整数平均值（C++代码）

完数（C语言代码）