本文共 1120 字，大约阅读时间需要 3 分钟。

Description

设有n个城市，依次编号为0，1，2，……，n-1（n<=100），另外有一个文件保存n个城市之间的距离(每座城市之间的距离都小于等于1000)。当两城市之间的距离等于-1时，表示这两个城市没有直接连接。求指定城市k到每一个城市i（0<=I,k<=n-1）的最短距离。

Input

第一行有两个整数n和k，中间用空格隔开；以下是一个NxN的矩阵，表示城市间的距离，数据间用空格隔开。

Output

输出指定城市k到各城市间的距离（从第0座城市开始，中间用空格分开）

Sample Input

3 1
0 3 1
3 0 2
1 2 0

Sample Output

3 0 2

解题思路

模板SPFA，但是要注意编号从0开始

#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int maxn=0x7fffffff;struct DT{   	int to,l,next;}a[30000];int dis[10000],head[10000],pd[6000],n,m,k,Gun=maxn,num;int h,t,v[10000],f[10000];void SPFA(int s){   	memset(dis,0x7f,sizeof(dis));	memset(f,0,sizeof(f));	h=0,t=1,v[1]=s,dis[s]=0,f[s]=1;	while(h++<t){   		for(int i=head[v[h]];i;i=a[i].next){   			if(dis[v[h]]+a[i].l<dis[a[i].to]){   				dis[a[i].to]=dis[v[h]]+a[i].l;				if(!f[a[i].to]){   					v[++t]=a[i].to;					f[a[i].to]=1;				}			}		}		f[v[h]]=0;			}}int main(){   	scanf("%d%d",&n,&m);	for(int i=1;i<=n;i++)		for(int j=1;j<=n;j++){   	    	int z;	    	scanf("%d",&z);	    	if(z>0)a[++num].to=j,a[num].l=z,a[num].next=head[i],head[i]=num;		}	SPFA(m+1);//粗暴	for(int i=1;i<=n;i++)	    printf("%d ",dis[i]);}