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-14 13:37
重庆大学 C++
点赞 评论 收藏
分享
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

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