题目链接
https://www.acwing.com/problem/content/description/3491/
题解
这道题的边权太大了,依靠着python无限制的整数才做出来,如果用c++就要换方法了
暴力
def dijkstra():
d=[1<<500 for i in range(n)]
d[0]=0
vis=[False for i in range(n)]
for _ in range(n):
minlength=1<<500
index=-1
for i in range(n):
if not vis[i] and d[i]<minlength:
index=i
minlength=d[i]
if index==-1:
break
vis[index]=True
for i in adj[index]:
v,w=i
if not vis[v] and d[v]>d[index]+w:
d[v]=d[index]+w
for i in range(1,n):
if vis[i]:
print(d[i]%100000)
else:
print(-1)
n,m=map(int,input().split())
adj=[[]for i in range(n)]
for i in range(m):
x,y=map(int,input().split())
dis=pow(2,i)
adj[x].append((y,dis))
adj[y].append((x,dis))
dijkstra()
并查集&快速幂&dijkstra
这道题目的边权,后一个比前面所有的加起来都多,最大可以达到1<<500,可能也只有python可以直接暴力做了
但是由于这个特性,好处就是可以得到一个结论,如果当前两个点在之前就是连通的,那么此时给出的边权绝对大于之前的连通长度,可以直接省略。连通性就可以用并查集来保证
边权可以使用快速幂来得到,最终答案需要取余,可以边求边权边取余
def quickm(a,b,m):
if b==0:
return 1
elif b%2==1:
cur=quickm(a,b//2,m)
return (a*cur*cur)%m
else:
cur=quickm(a,b//2,m)
return (cur*cur)%m
def find(x):
if x!=fa[x]:
fa[x]=find(fa[x])
return fa[x]
def dijksta():
d=[1<<31 for i in range(n)]
d[0]=0
vis=[False for i in range(n)]
for _ in range(n):
minlength=1<<31
index=-1
for i in range(n):
if not vis[i] and d[i]<minlength:
minlength=d[i]
index=i
if index==-1:
break
vis[index]=True
for i in adj[index]:
v,w=i
if not vis[v] and d[v]>d[index]+w:
d[v]=(d[index]+w)%mods
for i in range(1,n):
if d[i]>1<<30:
print(-1)
else:
print(d[i])
return
n,m=map(int,input().split())
fa=[i for i in range(n)]
adj=[[]for i in range(n)]
mods=100000
for i in range(m):
a,b=map(int,input().split())
faa=find(a)
fab=find(b)
if faa!=fab:
fa[faa]=fab
dis=quickm(2,i,mods)
adj[a].append((b,dis))
adj[b].append((a,dis))
dijksta()