B-旅行

B-旅行

https://ac.nowcoder.com/acm/problem/14550

最小路、枚举

题意:

图片说明
##分析:
版子题,枚举中间点,选两个最大的。注意图并不是连通图,选择的时候不能选自己。

代码:

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
typedef long long ll;
struct edge { int to, cost; };
typedef pair<int, int> pii;
const int max_n = 1100;
const int inf = 1e8;
int n, m;
int d[max_n];
vector<edge> G[max_n];

void dijstra(int s) {
    fill(d + 1, d + 1 + n, inf);
    priority_queue<pii, vector<pii>, greater<pii>> que;
    d[s] = 0;que.push({ d[s],s });
    while (!que.empty()) {
        pii p = que.top();que.pop();
        if (p.first > d[p.second])continue;
        for (int i = 0;i < G[p.second].size();i++) {
            int son = G[p.second][i].to;
            if (d[son] > d[p.second] + G[p.second][i].cost) {
                d[son] = d[p.second] + G[p.second][i].cost;
                que.push({ d[son],son });
            }
        }
    }
}


int main() {
    ios::sync_with_stdio(0);
    int t;cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 1;i <= n;i++)G[i].clear();
        for (int i = 1;i <= m;i++) {
            int a, b, c;cin >> a >> b >> c;
            G[a].push_back({ b,c });
            G[b].push_back({ a,c });
        }
        int ans = -1;
        for (int i = 1;i <= n;i++) {
            dijstra(i);int res = 0;int flag = 0;d[i] = inf;
            sort(d + 1, d + 1 + n, greater<int>());
            for (int j = 1;j <= n;j++) {
                if (d[j] != inf) { res += d[j]; flag++; }
                if (flag == 2)break;
            }if (flag == 2)ans = max(ans, res);
        }cout << ans << endl;
    }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-04 18:02
好不容易拿到了字节Offer,鼠鼠做后端的,但家里人觉得可能被裁员不稳定,让鼠鼠去投国企,现在好纠结到底该咋选
文档传偷助手:该投就投吧,不过建议别放弃offer 拿到手里的才是最好的
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
frutiger:逆天,我家就安阳的,这hr咋能说3k的,你送外卖不比这工资高得多?还说大厂来的6k,打发叫花子的呢?这hr是怎么做到说昧良心的话的
找工作时遇到的神仙HR
点赞 评论 收藏
分享
门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务