【题解】最短路径

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define N 101
using namespace std;
int w[N][N],dis[N],vis[N]; //w是边的权重 dis[]从起点到v点的最短路径
int n,s;
void Dijkstra(int x){//求从x到任一点的最短路径 
	memset(dis,INF,sizeof(dis));//dist[]=INF
	dis[x]=0;
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++){
		int j=0;
		for(int k=1;k<=n;k++){//找最小未被访问的dist[j]
			if(!vis[k]&&dis[k]<=dis[j]){
				j=k;
			}
		}
//		cout<<"J:"<<j<<endl;
		vis[j]=1;
		for(int k=1;k<=n;k++){//更新dis[j]
			if(w[j][k]){
				dis[k]=min(dis[k],dis[j]+w[j][k]);
			}	
		}
	}
}
int main(){
	bool f=0;
	cin>>n>>s;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>w[i][j];
		}
	}	
	Dijkstra(s);
	for(int i=1;i<=n;i++)
		if(i!=s)
			if(dis[i]<INF){
				cout<<dis[i]<<" ";
			}else{
				cout<<"-1"<<" ";
			}
	return 0;
}