- 科技
- 最短路
dijkstra
void
dijkstra()
{
memset(d
,0x3f,sizeof(d
));
memset(v
,0,sizeof(v
));
d
[1]=0;
q
.push(make_pair(0,1));
while(q
.sise())
{
int x
=q
.top();
if(v
[x
])continue;
v
[x
]=1;
for(int i
=head
[x
];i
;i
=e
[i
].next
)
{
int y
=e
[i
].to
;
if(d
[y
]>d
[x
]+e
[i
].z
)
{
d
[y
]=d
[x
]+e
[i
].z
;
q
.push(make_pair(-d
[y
],y
));
}
}
}
}
SPFA
添加链接描述
floyed
for(int k
=1;k
<=n
;k
++)
{
for(int i
=1;i
<=n
;i
++)
{
for(int j
=1;j
<=n
;j
++)
{
d
[i
][j
]|=d
[i
][k
]& d
[k
][j
];
}
}
}
Processed:
0.011, SQL:
8
