首页 > 其他分享 >day58-graph theory-part08-8.29

day58-graph theory-part08-8.29

时间:2024-08-30 12:57:33浏览次数:12  
标签:__ theory minDis graph day58 range inDegree curNode

tasks for today:

1. 拓扑排序 117.软件构建

2. dijkstra算法 47.参加科学大会

---------------------------------------------------------------------------------

1. 拓扑排序 117.软件构建

In this practice, it involves mainly the BFS method, which iteratively searching the current graph for current nodes which have the inDegree 0, signifying that it is currently the files that should be taken before proceeding any other files that should be executed based on it. Then after this file is added to the result list, the files it points to has to reduce the inDegree by 1, until all the files are selcted. Or, it will output the -1 signifying there is no doable paln.

from collections import defaultdict, deque

def main():
    n, m = map(int, input().split())
    
    inDegree = [0] * n
    pointTo = defaultdict(list)
    
    for _ in range(m):
        s, t = map(int, input().split())
        inDegree[t] += 1
        pointTo[s].append(t)
        
    bfsQueue = deque()
    
    for i in range(n):
        if inDegree[i] == 0:
            bfsQueue.append(i)
    
    result = []
    while bfsQueue:
        curNode = bfsQueue.popleft()
        result.append(curNode)
        curPointTo = pointTo[curNode]
        if curPointTo:
            for i in range(len(curPointTo)):
                inDegree[curPointTo[i]] -= 1
                if inDegree[curPointTo[i]] == 0:
                    bfsQueue.append(curPointTo[i])
    if len(result) == n:
        print(' '.join(map(str, result)))
    else:
        print(-1)
    
    return

if __name__ == "__main__":
    main()

2. dijkstra算法 47.参加科学大会

The idea of dijkstra is similar to prim algorithm in day 57.

After going through the entire process, each entry of the minDis records the minimum distance from the start point to current point.

def main():
    n, m = map(int, input().split())
    
    graph = [[float('inf')] * (n+1) for _ in range(n+1)]
    
    for _ in range(m):
        s, e, v  = map(int, input().split())
        graph[s][e] = v
        
    visited = [False] * (n+1)
    minDis = [float('inf')] * (n+1)
    
    start = 1
    end = n
    
    minDis[1] = 0
    
    for i in range(1, n+1):
        curMin = float('inf')
        curNode = 1
        
        for j in range(1, n+1):
            if not visited[j] and minDis[j] < curMin:
                curMin = minDis[j]
                curNode = j
                
        visited[curNode] = True
        
        for k in range(1, n+1):
            if not visited[k] and graph[curNode][k] != float('inf') and minDis[k] > curMin + graph[curNode][k]:
                minDis[k] = curMin + graph[curNode][k]
    
    if minDis[n] == float('inf'): 
        print(-1)
    else:
        print(minDis[n])
        
    return

if __name__ == "__main__":
    main()

标签:__,theory,minDis,graph,day58,range,inDegree,curNode
From: https://blog.csdn.net/bbrruunnoo/article/details/141676735

相关文章

  • QT在控件graphicsView中绘制箭头
    这里写自定义目录标题前言:基础夯实:成功效果展示:失败效果展示:核心代码:前言:对之前箭头没有成功绘制的补充,因为没有直接的箭头项,所以需要自己进行绘制基础夯实:可以直接看,建议看一下之前的绘制过程在控件graphicsView中实现绘图功能(一)在控件graphicsView中实现绘图功......
  • day57-graph theory-part07-8.28
    tasksfortoday:1.prim算法53.寻宝2.kruskal算法53.寻宝----------------------------------------------------------------------------1. prim算法53.寻宝Inthispractice,weseehowprimalgorithmisused.Theessenceofthispractice is:therearen......
  • 题解 [ABC199F] Graph Smoothing(中文/English)
    本题解提供英文版,位于示例代码之后。Englishversionofthiseditorialisprovidedafterthesamplecode.设行向量:\[A^{(k)}=\begin{bmatrix}a_1^{(k)}&a_2^{(k)}&\cdots&a_n^{(k)}\end{bmatrix}\]表示\(k\)次操作后每个节点点权的期望。特别地,\(A^{(0)}\)表......
  • CMake构建学习笔记8-OpenSceneGraph库的构建
    1.概论在连续构建了zlib、libpng、libjpeg、libtiff、giflib以及freetype这几个库之后,接下来我们就要来一个大的,构建OpenSceneGraph这样大型库。OpenSceneGraph(简称OSG)是一个高性能、跨平台的三维图形应用程序框架,广泛应用于科学可视化、模拟仿真、游戏开发等领域。理论上来说,......
  • C# split big picture into small pieces via graphics
    usingSystem;usingSystem.Collections.Generic;usingSystem.Drawing;usingSystem.Linq;usingSystem.Text;usingSystem.Threading.Tasks;usingSystem.Windows;usingSystem.Windows.Controls;usingSystem.Windows.Data;usingSystem.Windows.Documents;using......
  • 探索 graphrag-local-ollama:项目优势及实战应用
    目录引言一、项目背景与意义二、项目核心特性与优势三、详细的安装与使用步骤1.环境准备2.安装ollama3.下载所需模型4.克隆项目并安装依赖5.数据准备与初始化6.配置与构建索引7.执行查询四、项目的应用场景与未来展望结语引言在当今科技飞速发展的时代,人工......
  • 题解:UVA1479 Graph and Queries
    分析先看删边操作。由于并不保证是森林,所以我们没有好的方法来在线维护删边相关的操作。所以,我们可以套路地把询问离线,然后倒着操作。删边变成加边。需要注意的是权值的修改,记录时要把当前权值和修改的权值反过来。然后我们发现这个操作很经典,维护方式和[HNOI2012]永无乡......
  • Graphics2D绘图方法总结
    一、简介在开发中可能会遇到这样一类场景,业务复杂度不算太高,技术难度不算太深,但是做起来就很容易把人整破防,伤害很高侮辱性很强的:绘图。绘图最怕有人挑刺:这里变形,那里不对,全图失真。最近在处理这样一个场景,使用Java的Graphics2D类,绘制业务需要的图形模板,然后在具体流程中填充数......
  • 帮助我们从曲线图中获取数据的软件分享——GetData Graph Digitizer
    在科技论文写作和数据分析过程中,我们常常需要将自己的数据与前人的研究成果进行对比。然而,有时我们只能从别人的论文中获得一张包含坐标轴的曲线图,而无法直接获取原始数据。在这种情况下,GetDataGraphDigitizer软件就显得尤为重要。今天,我将详细介绍这款软件,帮助大家轻松......
  • Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Prediction
    目录概符号说明MotivationNeo-GNN代码Neo-GNNs:Neighborhoodoverlap-awaregraphneuralnetworksforlinkprediction.NeurIPS,2021.概一种计算上相对高效的,同时利用结构信息和特征信息的链接预测模型.符号说明\(\mathcal{G}=(\mathcal{V},\mathcal{E})\),gra......