最近在学习python,对于一个c系列语言深度中毒的人来说很多问题需要抛弃旧的认识并重新理解
#coding=utf-8 global n, m, k, edge, head, dis, stack, vis, nMax, mMax, inf nMax = 100 mMax = 10000 inf = 1e+10 class e(object): pass n = 0 k = 0 m = 0 eg = e() edge = [] head = [0] dis = [0] stack = [0] vis = [0] def addedge(a, b, c): global k, edge, head ed = e() ed.u = a #you can delect it ed.v = b ed.w = c ed.next = head[a] edge.append(ed) head[a]=k k+=1 pass def spfa(): global n, m, k, edge, head, dis, stack, vis,inf i = top = 0 for i in range(0 , n): dis[i] = inf vis[i] = 0 dis[0] = 0 vis[0] = 1 top+=1 stack[top] = 0 while(top!=0): u = stack[top] top-=1 i = head[u] while(i!=0): v = edge[i].v if dis[v] > dis[u]+edge[i].w: dis[v] = dis[u]+edge[i].w if(vis[v]==0): vis[v] = 1 top+=1 stack[top] = v i = edge[i].next vis[u] = 0 pass if __name__ == '__main__': u = v = l = i = 0 for i in range(0,nMax): head.append(0); dis.append(0) vis.append(0) stack.append(0) while(1): na = input() n = int(na) ma = input() m = int(ma) edge=[0] k = 1 for i in range(0,n): head[i] = 0 for i in range(0,m): ua = input() va = input() la = input() u = int(ua) v = int(va) l = int(la) addedge(u,v,l) spfa() for i in range(1,n): print(dis[i])
说一说遇到的问题吧
1python列表的长度不固定,当需要读取固定位置的元素时要确定那个位置非空
2python不支持“++”,c++中“num[index++]”这种写法在这里行不通
3输入int类型的值应该先input再用int()强制转换
4全局变量要用global申明,并在函数中也要用global申明
5说一个很邪门的事情
''' Created on 2014年7月5日 @author: bbezxcy ''' global stu,k class student: pass stu = [] def addStudent1(nm ,ag): global stu,k stu[k].name = nm stu[k].age = ag k+=1 pass def addStudent(nm ,ag): global stu,k stu[k].name = nm stu[k].age = ag k+=1 pass if __name__ == '__main__': num = 0 k = 0 strn = input("请输入学生人数") num = int(strn) ss = student() for i in range(0 ,num): stu.append(ss) for i in range(0 ,num): nm = input() ag = input() addStudent(nm ,ag) for i in range(0,num): print(stu[i].name) print(stu[i].age)
这是一个简单的向list中插入学生信息的程序。但是运行时候会发现,最后插入的值会覆盖前面的学生信息值
打印结果如下
请输入学生人数3 zys 20 xcy 19 ghz 20 输出结果 ghz 20 ghz 20 ghz 20
把addstudent改为
def addStudent(nm ,ag): global stu,k s = student() s.name = nm s.age = ag stu.append(s) k+=1 pass
后问题解除
相关推荐
SPFA入门,很好的入门指南。值得一下!
spfa算法的java实现
最短路SPFA算法。SPFA(Shortest Path Faster Algorithm)算法是求单源最短路径的一种算法,它是Bellman-ford的队列优化,它是一种十分高效的最短路算法。存在负权边时使用。
使用C++实现的Queue improved Bellman-Ford单源最短路算法,在国内还被叫做SPFA。这个程序输入一个图,找到图中的一个点,这个点到最远点的长度最短。图使用邻接表保存。
SPFA算法 此处为SPFA算法详解 用dis数组记录源点到有向图上任意一点距离,其中源点到自身距离为0,到其他点距离为 INF。将源点入队,并重复以下步骤: 1、队首x出队 2、遍历所有以队首为起点的有向边(x,i),若...
SPFA算法,acm常用的算法,求最短路径
SPFA算法优化及应用,SPFA算法优化及应用,SPFA算法优化及应用
基本思想 用一个队列来进行维护。初始时将源加入队列。每次从队列中取出一个元素,并对所有与他相邻的点进行松弛,若某个相邻的点松弛成功,则将其入队。...d[i]:起点s到i的临时最短路长度 松驰的结果是使j的d值减小
现在网上有很多最短路径的算法,C++版本的较多,java可用的demo较少,或者不支持双向的,这里总结了java版的spfa算法,个人认为此算法比较实用(拓扑、GIS定位等项目上),本算法支持双向,有兴趣的可以下载下来研究...
SPFA算法 C++实现,使用邻接表存图
求单源最短路的SPFA算法的全称是:Shortest Path Faster Algorithm。 SPFA算法是西南交通大学段凡丁于1994年发表的. 从名字我们就可以看出,这种算法在效率上一定有过人之处。 很多时候,给定的图存在负权边,这时...
NULL 博文链接:https://128kj.iteye.com/blog/1716385
算法合集之《SPFA算法的优化及应用》.pdf
SPFA算法就解决了重复计算的问题,在大数据面前大大减少运行时间 该算法改善的思想是避免顶点进行无效的重复更新,对有待更新的顶点移入队列,已更新的顶点移出队列,避免待更新的顶点中存在重复顶点
这个是关于SPFA最短路径一些相关东西。。
这里面的内容是个PPT,介绍的很好,如果你想更加的清楚 SPFA 和Bellman_ford.ppt 最短路算法的原理,这是个不错的选择
本资料详细的介绍了SPFA算法的优化及应用。 深入浅出。 你值得拥有。
图论- 最短路- Bellman-Ford 算法与 SPFA.rar
自己打的spfa算法板子。包含邻接表的两种形式,邻接矩阵Map;此代码不完全,(使用是要注释掉部分的)在使用时要结合题意更改。望采纳!
SPFA算法 算法简介 简介.docx