等待戈多 （C++代码）

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<algorithm>
#define MAX 99999
using namespace std;

double m[500+1][500+1]; 
double dis[500+1];
int S[500+1];
int n,k;

void dijkstra(int star){
	//初始化dis 
	for(int i=1; i<=n; i++) dis[i]=m[star][i];
	S[star]=1;
	
	for(int i=1; i<=n-1; i++){
		//找出S集合外，距离原点最近的点 
		double mint=MAX;
		for(int j=1; j<=n; j++){
			if(S[j]==0 && mint>dis[j]){
				mint=dis[j];
				star=j;
			}
		}
		S[star]=1;
		
		//更新dis
		for(int j=1; j<=n; j++)
			dis[j]=min(dis[j],dis[star]+m[star][j]);
	} 
}

int main(){
	cin>>n>>k;

	for(int i=1; i<=n; i++ ){
		for(int j=1; j<=n; j++){
			cin>>m[i][j];
			if(m[i][j]==0)  m[i][j]=MAX;
		}
		S[i]=0;
	}
	
	double v;
	for(int i=1; i<=n; i++ ){
		for(int j=1; j<=n; j++){
			cin>>v;
			if(v!=0) m[i][j]/=v; //权重变为时间 
		}
	}
	
	dijkstra(1); 
	printf("%.2lf\n",dis[k]);
	return 0;
}