首页 > 其他分享 >最爱的城市

最爱的城市

时间:2022-11-28 20:02:17浏览次数:30  
标签:dist int 城市 nextInt 最爱 input 线段 输入


最爱的城市


时间限制:1 秒

内存限制:32 兆

特殊判题:

标签

  • Floyd最短路径

题目描述

一天小明捧着一本世界地图在看,突然小明拿起笔,将他最爱的那些城市标记出来,并且随机的将这些城市中的某些用线段两两连接起来。
小明量出了每条线段的长度,现在小明想知道在这些线段组成的图中任意两个城市之间的最短距离是多少。

输入格式

输入包含多组测试数据。
每组输入第一行为两个正整数n(n<=10)和m(m<=n*(n-1)/2),n表示城市个数,m表示线段个数。
接下来m行,每行输入三个整数a,b和l,表示a市与b市之间存在一条线段,线段长度为l。(a与b不同)
每组最后一行输入两个整数x和y,表示问题:x市与y市之间的最短距离是多少。(x与y不同)
城市标号为1~n,l<=20。

输出

对于每组输入,输出x市与y市之间的最短距离,如果x市与y市之间非连通,则输出“No path”。

样例输入

4 4
1 2 4
1 3 1
1 4 1
2 3 1
2 4

样例输出

3

【分析】

,求出各顶点到其他顶点的最短路径。

用java语言编写程序,代码如下:

import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(new BufferedInputStream(System.in));
final int INF = 1000;
while(input.hasNext()) {
int n = input.nextInt();
int m = input.nextInt();

int[][] dist = new int[n + 1][n + 1];
for(int i = 0; i < n + 1; i++)
Arrays.fill(dist[i], INF);

int a, b, len;
for(int i = 0; i < m; i++) {
a = input.nextInt();
b = input.nextInt();
len = input.nextInt();
dist[a][b] = dist[b][a] = len;
}

int x = input.nextInt();
int y = input.nextInt();
floyd(n, dist);
if(dist[x][y] == INF)
System.out.println("No path");
else
System.out.println(dist[x][y]);
}
}

public static void floyd(int n, int[][] dist) {
for(int k = 1; k <= n; k++)
for(int u = 1; u <= n; u++)
for(int v = 1; v <= n; v++)
if(dist[u][v] > dist[u][k] + dist[k][v])
dist[u][v] = dist[u][k] + dist[k][v];
}
}



标签:dist,int,城市,nextInt,最爱,input,线段,输入
From: https://blog.51cto.com/u_15894233/5893618

相关文章

  • 智慧型可视化综合管理平台,全方位打造数字孪生城市
    随着人工智能、大数据、物联网、云计算、区块链等信息技术的快速发展,智慧化管理正在成为城市运营的全新方式。北京深圳等一些一线城市已经率先开始城市运营数字化升级的工......
  • 大数据在智慧城市的建设中起到了哪些作用?_光点科技
    智慧城市是一个大趋势,许多大中小城市正在探索发展,因为智慧城市建设不仅可以促进城市的发展,而且可以有效地处理“大城市病”,能有效提高城市居民的生活质量。但在智慧城市的建......
  • 不用某度、某德个性地图编辑器,用Python几行代码绘制任何地区的风格化城市肌理
    原创:Ing_ideas话不多说先上图:1.OSMnx简介OSMnx是Python的一个包,建立在GeoPandas、NetworkX和matplotlib之上,可以调用OpenStreetMap的地图数据,所以不限......
  • uview 腾讯地图城市选择器
    //引入SDK核心类varQQMapWX=require('@/common/qqmap.js');//实例化API核心类varqqmapsdk=newQQMapWX({key:'DIWAZ-OWFC2-MXZUQ-C3WF......
  • Luogu P1453 城市环路(基环树DP)
    法一:dsu#include<bits/stdc++.h>usingll=longlong;usingnamespacestd;constintN=100010;structnode{intv,nxt;}e[N......
  • 小城市里,也有原型
    在产品经理手中,如同吃饭睡觉一般熟练的原型工具,对于茫茫大众来说,可能是个一生都不会有交集的名词。即使站在专业的高峰,如Axure,对于行外人来说,也是从未听说过的名字。即使有......
  • 高德地图POI分类和城市列表
    高德地图POI分类和城市列表高德地图对POI一共有三级分类(大类、中类、小类),其中一级分类有23个,二级分类有267个,三级分类有869个。分类文档的下载网址参见:https://lbs.amap......
  • 数字经济城市一二线分布
    数据来源:2022中国数字经济发展研究报告-赛迪顾问数字经济一线城市[5个]综合经济实力及数宇经济水平均领跑全国,呈现多维全面发展态势北京上海深圳杭州广州数字......
  • 广州华锐互动|构建智慧城市数字化三维实景建模平台
    在技术日新月异的时代,智慧城市建设发展也在不断推进,从物理世界到虚拟世界,人们对于未来城市的构想正在智慧城市中逐步实现。智慧城市的构建离不开物联网、人工智能、虚拟现......
  • 三维 GIS 可视化技术在城市管理中的作用
    伴随着我国城市人口数量的持续猛增,资源、设备与人口数量的空间布局对城市化基本建设起着愈来愈关键的影响。三维室内空间的合理认知日渐变成城市整体规划和管理方法的关键......