牛客14352 旅行解题报告

YZL11111 · 2019-10-26 15:52:46 · 个人记录

题目链接：https://ac.nowcoder.com/acm/problem/14352

【题目描述】

小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

【解题思路】

预处理出所有点到其他点的最短路，枚举中间点k使得总距离最大

【AC代码】

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x7fffffff;
inline int read()
{
    register int X = 0, w = 0; register char ch = 0;
    while (!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
    while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
    return w ? -X : X;
}
const int maxn = 1010 * 2;
int G[maxn][maxn];
struct Edge
{
    int to;
    int next;
    int w;
}edge[maxn];
int head[maxn];
bool vis[maxn];
int cnt, n, m;
inline void insert(int u, int v, int w)
{
    ++cnt;
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    edge[cnt].w = w;
    head[u] = cnt;
}
inline void Dijkstra(int s)
{
    priority_queue< pair<int, int> > que;
    que.push(make_pair(0, s));
    G[s][s] = 0;
    for (register int i = 1; i <= n; ++i) vis[i] = false;
    while (!que.empty())
    {
        int u = que.top().second;
        que.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (register int i = head[u]; i; i = edge[i].next)
        {
            int v = edge[i].to;
            if (G[s][v] > G[s][u] + edge[i].w)
            {
                G[s][v] = G[s][u] + edge[i].w;
                que.push(make_pair(-G[s][v], v));
            }
        }
    }
}
inline void init()
{
    memset(head, 0, sizeof(head));
    for (register int i = 1; i <= n; ++i)
    {
        for (register int j = 1; j <= n; ++j)
        {
            if (i == j) G[i][j] = 0;
            else G[i][j] = INF;
        }
    }
    cnt = 0;
}
int main()
{
    register int t;
    scanf("%d", &t);
    while (t--)
    {
        n = read();
        m = read();
        init();
        for (register int i = 1; i <= m; ++i)
        {
            register int u, v, w;
            u = read();
            v = read();
            w = read();
            insert(u, v, w);
            insert(v, u, w);
        }
        register int ans = -1;
        for (register int i = 1; i <= n; ++i) Dijkstra(i);
        for (register int i = 1; i <= n; ++i)
        {
            register int s1 = 0, s2 = 0, Max = 0;
            for (register int j = 1; j <= n; ++j)
            {
                if (G[j][i] != INF && G[j][i] > Max)
                {
                    Max = G[j][i];
                    s1 = j;
                }
            }
            Max = 0;
            for (register int j = 1; j <= n; ++j)
            {
                if (j == s1)continue;
                if (G[i][j] != INF && G[i][j] > Max)
                {
                    Max = G[i][j];
                    s2 = j;
                }
            }
            if (s1 && s2)
            {
                register int t = G[s1][i] + G[i][s2];
                ans = ans < t ? t : ans;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

牛客14352 旅行 解题报告