最短路模板（持续更新）

最短路题目（持续更新）

(1.) (Silver) (Cow) (Party) （需要该篇博文的阅读密码）

(2.) 改造路 (Revamping) (Trails)

(3.) 冻结

(4.) 飞行路线

非负权单源最短路径

$View$ $Code$

```cpp void dijkstra(int s) { memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); priority_queue > q; dis[s]=0; q.push(make_pair(0,s)); while(!q.empty()) { int x=q.top().second; q.pop(); if(vis[x]) continue; vis[x]=1; for(register int i=head[x];i;i=e[i].nxt) { int y=e[i].ver,w=e[i].w; if(dis[x]+w

任意两点间最短路径

$View$ $Code$

int n,m,x,y,f[1005][1005];
void floyd()
{
	for(register int k=1;k<=n;k++)
		for(register int i=1;i<=n;i++)
			for(register int j=1;j<=n;j++)
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
int main()
{
	n=read();
	m=read();
	memset(f,0x3f,sizeof(f));
	for(register int i=1;i<=n;i++)
		f[i][i]=0;
	for(register int i=1;i<=m;i++)
	{
		x=read();
		y=read();
		f[x][y]=min(f[x][y],1);
		f[y][x]=min(f[y][x],1);
	}
	floyd();
	return 0;
}