2025年旅行

2025年旅行

科技前沿 • 2025-02-24 16:27 • 阅读 40

大家好，我是讯享网，很高兴认识大家。

小z放假了，准备到RRR城市旅行，其中这个城市有N个旅游景点。小z时间有限，只能在三个旅行景点进行游玩。小明租了辆车，司机很善良，说咱不计路程，只要你一次性缴费足够，我就带你走遍RRR城。

小z很开心，直接就把钱一次性缴足了。然而小z心机很重，他想选择的路程尽量长。

然而司机也很聪明，他每次从一个点走到另外一个点的时候都走最短路径。

你能帮帮小z吗？

讯享网

需要保证这三个旅行景点一个作为起点，一个作为中转点一个作为终点。（一共三个景点，并且需要保证这三个景点不能重复）.

输入描述:
本题包含多组输入，第一行输入一个整数t，表示测试数据的组数
每组测试数据第一行输入两个数N,M表示RRR城一共有的旅游景点的数量，以及RRR城中有的路的数量。
接下来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

#include <bits/stdc++.h> using namespace std; const int maxn = 1007; int d[maxn], head[maxn], tol, n, m; bool vis[maxn]; queue<int> P; struct node { 
    int to, cost, next; }rode[maxn * 2]; void add(int a, int b, int c) { 
    rode[tol].to = b; rode[tol].cost = c; rode[tol].next = head[a]; head[a] = tol++; } int spfa(int st) { 
    for (int i = 0; i < maxn; i++) d[i] = 1e9; d[st] = 0; memset(vis, 0, sizeof(vis)); vis[st] = 1; P.push(st); while (!P.empty()) { 
    int v = P.front(); P.pop(); vis[v] = 0; for (int i = head[v]; i != -1; i = rode[i].next) { 
    node e = rode[i]; if (d[e.to] > d[v] + e.cost) { 
    d[e.to] = d[v] + e.cost; if (!vis[e.to]) { 
    P.push(e.to); vis[e.to] = 1; } } } } int ma1 = -1, ma2 = -1; d[st] = -3; for (int i = 1; i <= n; i++) { 
    if (d[i] == 1e9) continue; if (d[i] > ma1) ma2 = ma1, ma1 = d[i]; else if (d[i] > ma2) ma2 = d[i]; } if (ma1 != -1 && ma2 != -1) return ma1 + ma2; return -1; } int main() { 
    int T; scanf("%d", &T); while (T--) { 
    tol = 0; memset(head, -1, sizeof(head)); scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { 
    int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); add(b, a, c); } int ma = -1; for (int i = 1; i <= n; i++) ma = max(ma, spfa(i)); printf("%d\n", ma); } return 0; }

讯享网

相关推荐