首页 > 其他分享 >NC14352 旅行

NC14352 旅行

时间:2023-01-02 22:12:20浏览次数:72  
标签:旅行 NC14352 int 中转 景点 输入 dis

题目链接

题目

题目描述

小z放假了,准备到R城市旅行,其中这个城市有N个旅游景点。小z时间有限,只能在三个旅行景点进行游玩。小明租了辆车,司机很善良,说咱不计路程,只要你一次性缴费足够,我就带你走遍R城。
小z很开心,直接就把钱一次性缴足了。然而小z心机很重,他想选择的路程尽量长。
然而司机也很聪明,他每次从一个点走到另外一个点的时候都走最短路径。
你能帮帮小z吗?
需要保证这三个旅行景点一个作为起点,一个作为中转点一个作为终点。(一共三个景点,并且需要保证这三个景点不能重复).

输入描述

本题包含多组输入,第一行输入一个整数t,表示测试数据的组数
每组测试数据第一行输入两个数N,M表示R城一共有的旅游景点的数量,以及R城中有的路的数量。
接下来M行,每行三个数,a,b,c表示从a景点和b景点之间有一条长为c的路
t<=40
3<=N,M<=1000
1<=a,b<=N
1<=c<=100

输出描述

每组数据包含一行,输出一个数,表示整条路程的路长。
如果找不到可行解,输出-1.

示例1

输入

4
7 7
1 2 100
2 3 100
1 4 4
4 5 6
5 6 10
1 6 4
6 7 8
7 3
1 2 1
1 3 1
1 3 2
7 3
1 2 1
3 4 1
5 6 1
8 9
1 2 1
2 3 1
3 4 1
4 1 1
4 5 1
5 6 1
6 7 1
7 8 1
8 5 1

输出

422
3
-1
9

说明

请注意这是一个稀疏图.

题解

知识点:最短路。

把每个点当作中转点跑最短路,最长和次长距离即这个中转点的答案,取每个点的最大值即可。

时间复杂度 \(O(n(n+m)\log m)\)

空间复杂度 \(O(n+m)\)

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 1007, M = 1007 << 1;

int n, m;

struct edge {
    int v, nxt, w;
}e[M];
int h[N], idx;
void add(int u, int v, int w) {
    e[++idx] = edge{ v,h[u],w };
    h[u] = idx;
}

int dis[N];
bool vis[N];
struct node {
    int v, w;
    friend bool operator<(node a, node b) {
        return a.w > b.w;
    }
};
priority_queue<node> pq;
void dijkstra(int st) {
    for (int i = 1;i <= n;i++) dis[i] = 0x3f3f3f3f, vis[i] = 0;
    dis[st] = 0;
    pq.push({ st,0 });
    while (!pq.empty()) {
        int u = pq.top().v;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = h[u];i;i = e[i].nxt) {
            int v = e[i].v, w = e[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                pq.push(node{ v,dis[v] });
            }
        }
    }
}

bool solve() {
    cin >> n >> m;
    idx = 0;
    for (int i = 1;i <= n;i++) h[i] = 0;
    for (int i = 1;i <= m;i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);
    }
    int ans = -1;
    for (int i = 1;i <= n;i++) {//枚举中转点,找到最大和次大两条
        dijkstra(i);
        int mx = 0, smx = 0;
        for (int j = 1;j <= n;j++) {
            if (dis[j] == 0x3f3f3f3f) continue;
            if (mx < dis[j]) {
                smx = mx;
                mx = dis[j];
            }
            else if (smx < dis[j]) {
                smx = dis[j];
            }
        }
        if (mx && smx) ans = max(ans, mx + smx);
    }
    cout << ans << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

标签:旅行,NC14352,int,中转,景点,输入,dis
From: https://www.cnblogs.com/BlankYang/p/17020680.html

相关文章

  • 遗传算法解决旅行商问题(TSP)
    遗传算法解决旅行商问题作者:Cukor丘克环境:MatlabR2020a+vscode问题描述旅行商问题(TSP).一个商人欲从自己所在的城市出发,到若干个城市推销商品,然后回到其所在的城市......
  • 算法--旅行者过河问题
    1.题目在漆黑的夜里,四位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话,大家是无论如何也不敢过桥去的。不幸的是,四个人一共只带了一只手电筒,而桥窄得只够......
  • P1523 旅行商简化版
    简化题意:给定\(n\)个点,要求从最左端的点到最右端的点之间寻找两条互不重复的路径,两条路径经过所有点,且路径长度最小。输出最短路径长度。思路:动态规划。应该也算比较......
  • [JSOI2013]旅行时的困惑
    链接:https://www.luogu.com.cn/problem/P5258题目描述:给定一颗有向树,求至少多少条有向路径可以覆盖整颗树(有向路径可以相交)题解:路径的覆盖,我们容易想到赛道修建那样的......
  • 「NOIP2012」开车旅行
    「NOIP2012」开车旅行题面描述:小\(A\)与小\(B\)开车旅行,两个点的距离是两个点的高度的差的绝对值,若两个点的距离相同,则认为海拔低的要更近,小\(A\)以离他次近的点作......
  • [JSOI2013]旅行时的困惑
    链接:https://www.luogu.com.cn/problem/P5258题目描述:给定一颗有向树,求至少多少条有向路径可以覆盖整颗树(有向路径可以相交)题解:路径的覆盖,我们容易想到赛道修建那样......
  • [JSOI2010]旅行
    链接:https://www.luogu.com.cn/problem/P6029题目描述:给定一个$n$个$m$条边的无向图,可以交换$k$组边,求$1$到$n$的最短路。题解:发现值域都比较小,考虑$dp$。我们可以......
  • python奇妙旅行之4行代码生成图像验证码
    在学习的路上,永无止境。就好比人掉进"深渊",永远无法自拔!  ~ ~!我没有开车,我没有开车~~~今天空闲时间再看某大佬得论坛,被点了一下,就想起来了2种方法,生成图片验证码,简约......
  • 2022 最新海南岛旅行攻略 All In One
    2022最新海南岛旅行攻略AllInOne海南岛面积约3.54万平方公里,人口约940多万。人口GDPhttps://www.hainan.gov.cn/hainan/zfsj/xsj.shtmlhttps://www.hainan.......
  • 1088. 旅行问题
    题目链接1088.旅行问题John打算驾驶一辆汽车周游一个环形公路。公路上总共有\(n\)个车站,每站都有若干升汽油(有的站可能油量为零),每升油可以让汽车行驶一千米。John......