蓝桥公园——JAVA

简介: 蓝桥公园——JAVA

 题目链接:

题目描述

小明喜欢观景,于是今天他来到了蓝桥公园。

已知公园有 N 个景点,景点和景点之间一共有 M条道路。小明有 Q个观景计划,每个计划包含一个起点 st和一个终点 ed,表示他想从 stst 去到 ed。但是小明的体力有限,对于每个计划他想走最少的路完成,你可以帮帮他吗?

输入描述

输入第一行包含三个正整数 N,M,Q

第 2 到 M + 1 行每行包含三个正整数 u,v,w表示 vu↔v 之间存在一条距离为 w 的路。

第 M+2 到 M + Q-1 行每行包含两个正整数 st,ed,其含义如题所述。

输出描述

输出共 Q 行,对应输入数据中的查询。

若无法从 st 到达 eded 则输出 −1。

输入输出样例

示例 1

输入

3 3 3
1 2 1
1 3 5
2 3 2
1 2
1 3
2 3

image.gif

输出

1
3
2

image.gif

运行限制

语言 最大运行时间 最大运行内存
C++ 1s 256M
C 1s 256M
Java 3s 256M
Python3 50s 256M

JAVA:

import java.util.Arrays;
import java.util.Scanner;
public class 蓝桥公园 {
    private static final long INF = 0x3f3f3f3f3f3f3f3fL;
    private static final int N = 405;
    private static long[][] dp = new long[N][N];
    private static int n, m, q;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        q = scanner.nextInt();
        for (long[] row : dp) {
            Arrays.fill(row, INF);
        }
        for (int i = 0; i < m; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            long w = scanner.nextLong();
            dp[u][v] = dp[v][u] = Math.min(dp[u][v], w);
        }
        floyd();
        while (q-- > 0) {
            int s = scanner.nextInt();
            int t = scanner.nextInt();
            if (dp[s][t] == INF) {
                System.out.println(-1);
            } else if (s == t) {
                System.out.println(0);
            } else {
                System.out.println(dp[s][t]);
            }
        }
    }
    private static void floyd() {
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
                }
            }
        }
    }
}

image.gif

C/C++:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 405;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
ll dis[N][N];
int n, m, q;
int main()
{
    cin >> n >> m >> q;
    memset(dis, 0x3f, sizeof dis);
    for (int i = 1; i <= n; i++) dis[i][i] = 0;
    for (int i = 1; i <= m; i++) {
        ll u, v, w; cin >> u >> v >> w;
        dis[u][v] = dis[v][u] = min(dis[u][v], w); // 防止出现重边
    }
    // floyd
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    // 输出
    int s, t;
    for (int i = 0; i < q; i++) {
        cin >> s >> t;
        ll ans = dis[s][t] == INF ? -1 : dis[s][t];
        cout << ans << endl;
    }
    return 0;
}

image.gif


目录
打赏
0
0
0
0
2
分享
相关文章
python中socket客户端发送和接收数据
【4月更文挑战第7天】本教程聚焦TCP客户端数据发送与接收。使用Python的`socket`模块,通过`send()`发送字节串至服务器,如`client_socket.send(message_bytes)`;用`recv()`接收数据,如`received_data = client_socket.recv(buffer_size)`。异常处理确保网络错误时程序健壮性,例如`try-except`捕获`socket.error`。理解和掌握这些基础操作对于构建稳定的TCP客户端至关重要。
2148 1
Linux平台Unity下RTMP|RTSP低延迟播放器技术实现
本文介绍了在国产操作系统及Linux平台上,利用Unity实现RTMP/RTSP直播播放的方法。通过设置原生播放模块的回调函数,可将解码后的YUV数据传递给Unity进行渲染,实现低延迟播放。此外,还提供了播放器启动、参数配置及停止的相关代码示例,并概述了如何在Unity中更新纹理以显示视频帧。随着国产操作系统的发展,此类跨平台直播解决方案的需求日益增长,为开发者提供了灵活高效的开发方式。
209 6
内附原文|SIGMOD’24:百万核的智能调度,云数仓如何结合AI处理用户混合负载
论文提出的Flux通过使用AI技术将短时和长时查询解耦进行自动弹性,解决了云数据仓库的性能瓶颈,同时支持了资源按需预留。Flux优于传统的方法,查询响应时间 (RT) 最多可减少75%,资源利用率提高19.0%,成本开销降低77.8%。
内附原文|SIGMOD’24:百万核的智能调度,云数仓如何结合AI处理用户混合负载
sqlite3自动插入创建时间和更新时间
在本文中,作者分享了如何在SQLite3中实现类似MySQL和Postgres的几个基本功能。首先,通过`AUTOINCREMENT`关键字设置了主键ID自增。接着,通过`DEFAULT (DATETIME(&#39;now&#39;, &#39;localtime&#39;))`确保了`created_at`在数据插入时自动获取当前时间。然而,`updated_at`在数据更新时不自动更新,为解决这个问题,作者创建了一个触发器(`trigger_position_info_updated_at`),在更新数据后自动更新`updated_at`字段。
261 0
C语言取整方法详解
C语言取整方法详解
2068 0
[Eigen中文文档] 固定大小的可向量化Eigen对象
本文主要解释 固定大小可向量化 的含义。
206 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等