当前位置: 首页 > news >正文

西安网站建设网如何诚信网站平台建设

西安网站建设网,如何诚信网站平台建设,幸福人寿保险公司官方网站电子保单打印,wordpress 是什麽dijsktra算法模板: def dijkstra(x):#x表示出发点dis[inf]*n #dis记录从x出发到各个点的最短距离,初始化为infdis[x]0 #源点到自己的距离为0vis[False]*n #检查各个点是否访问过for _ in range(n-1): #检查除了源点的其他n-1个点,更新dis…

dijsktra算法模板:

def dijkstra(x):#x表示出发点dis=[inf]*n #dis记录从x出发到各个点的最短距离,初始化为infdis[x]=0    #源点到自己的距离为0vis=[False]*n #检查各个点是否访问过for _ in range(n-1): #检查除了源点的其他n-1个点,更新disnode=-1 #开始假设不知道谁是离源点最近的点for j in range(n):#循环查找谁是离源点最近的那个点if not vis[j] and (node==-1 or dis[j]<dis[node]):node=jfor j in range(n):#对node的邻居点进行松弛处理dis[j]=min(dis[j],dis[node]+g[node][j])vis[node]=True #对node点标记为已访问

​​​​​​​743. 网络延迟时间
因为本题的节点是从1到n,所以最后把dis数组中的第一个忽略掉(dis[1:])

然后就是经典的dijkstra最短路径算法,套用模板即可。

class Solution:def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:g=[[inf]*(n+1) for _ in range(n+1)]for x,y,w in times:g[x][y]=wdis=[inf]*(n+1)dis[k]=0vis=[False]*(n+1)for _ in range(n):x=-1for i in range(1,n+1):if not vis[i] and (x==-1 or dis[i]<dis[x]):x=ifor i in range(1,n+1):dis[i]=min(dis[i],dis[x]+g[x][i])vis[x]=Trueans=max(dis[1:])return ans if ans!=inf else -1

2642. 设计可以求最短路径的图类
又是dijkstra最短路径算法,这里需要判断一下能否到达终点的问题:

class Graph:def __init__(self, n: int, edges: List[List[int]]):self.n=nself.g=[[float("INF")]*n for _ in range(self.n)]for x,y,cost in edges:self.g[x][y]=costdef addEdge(self, edge: List[int]) -> None:self.g[edge[0]][edge[1]]=edge[2]def shortestPath(self, node1: int, node2: int) -> int:n=len(self.g)dis=[float('INF')]*ndis[node1]=0vis=[False]*nwhile 1:x=-1for i,(b,d) in enumerate(zip(vis,dis)):if not b and (x<0 or d<dis[x]):x=iif x<0 or dis[x]==float('INF'):return -1if x==node2:return dis[x]vis[x]=Truefor y,w in enumerate(self.g[x]):if dis[x]+w<dis[y]:dis[y]=dis[x]+w# Your Graph object will be instantiated and called as such:
# obj = Graph(n, edges)
# obj.addEdge(edge)
# param_2 = obj.shortestPath(node1,node2)

1334. 阈值距离内邻居最少的城市
枚举每个点作为出发点,算法返回小于等于阈值的数目即可。

因为题目要求返回数量最少且编号最大的点,所以从n-1到0遍历即可。

class Solution:def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:g=[[inf]*n for _ in range(n)]for x,y,w in edges:g[x][y]=wg[y][x]=w#枚举每个点作为出发点,做dijkstra算法def dijkstra(x):dis=[inf]*ndis[x]=0vis=[False]*nfor _ in range(n-1):node=-1for j in range(n):if not vis[j] and (node==-1 or dis[j]<dis[node]):node=jfor j in range(n):dis[j]=min(dis[j],dis[node]+g[node][j])vis[node]=Truereturn sum(d<=distanceThreshold for d in dis)ans,cnt=n,inf    for i in range(n-1,-1,-1):if dijkstra(i)<cnt:cnt=dijkstra(i)ans=ireturn ans

http://www.yayakq.cn/news/771471/

相关文章:

  • 购物网站建设需要多少钱yw55523can优物入口
  • 营销型网站的公司网站视频下载软件
  • 检察院门户网站建设工作成效数字化营销与传统营销的区别
  • 做网站记者好吗seo网站优化培训怎么样
  • 新手学做免费网站软件网站作业成品
  • 网站排名突然掉没了app平台开发费用
  • 吴江建设局网站打不开seo系统
  • 网站制作公司杭州佛山专业网站建设公司
  • 网站建设不足之处dw可以做有后台的网站么
  • 怎么做关不掉的网站建站行业获客
  • 大兴网站建设设计公司ecilpse做网站
  • 网站开发培训北京宁波网站建设的企业
  • 河南郑州建设网站制作小型购物网站开发费用
  • 国内品牌营销成功案例seo管理工具
  • 运营一个网站的成本深圳物流公司收费标准
  • 凡客诚品网站设计特点免费外贸网站源码
  • 湛江网站制作江网站制作货运代理东莞网站建设
  • 网销都是在那些网站做推广网站开发前后端工具组合
  • 北京网站建设维护上海网站优化推广公司
  • 怎样看网站的建设时间表四川企业网站开发
  • 西宁建一个网站公司南京最好的网站设计公司
  • 顺企网我做网站做网站手机
  • 哪个公司网站做的好如何制作自己的官网
  • 苏州高端网站制作官网什么是网络营销中的免费营销策略
  • 二级域名做网站好不好老域名新网站推广
  • 彩票网站和app建设wordpress备案申请
  • 西安市建设局网站网站建设汽车后市场解决方案
  • 网站开发人员招聘广告语外贸网络推广的方式
  • 网站建设工作总结报告做网站有一个火箭回顶部
  • 济南做网站公司有哪些网站站建设建设中页中页