等待戈多 （C语言代码）

解题思路:用dijkstra算法解决该题。

注意事项:无

参考代码:

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

#include<string.h>

int main(){

     int n,k;

     float v[503][503],t[503][503];

    while(~scanf("%d %d ",&n,&k)){

         for (int i=1;i<n+1;i++) {

             for (int j=1;j<n+1;j++) {

                 scanf("%f",&t[i][j]);

             }

         }

         for (int i=1;i<n+1;i++) {

             for (int j=1;j<n+1;j++) {

                 scanf("%f",&v[i][j]);

                 if (v[i][j]!=0) t[i][j]=t[i][j]/v[i][j];

                 else t[i][j]=0;

             }

         }

         for (int i=1;i<n;i++) {

             if (i==k) {

             for (int j=k+1;j<n;j++) {

                     t[i][j]=t[n][j];

                 }

             } else {

                 float tmp=0;

                 tmp=t[i][k];

                 t[i][k]=t[i][n];

                 t[i][n]=tmp;

             }

         }

             int i=3;

             while (i!=n){

             int q=i+1;

             for (int j=2;j<i;j++) {

                 if (t[1][i]>t[1][j]+t[j][i]) t[1][i]=t[1][j]+t[j][i];

             }

             for (int j=i-1;j>1;j--) {

                 if (t[1][j]>t[1][i]+t[j][i]) {

                     t[1][j]=t[1][i]+t[j][i];

                     q=j;

                 } 

             }

             i=q;

         }

        printf("%.2f",t[1][n]);

     }

    return 0;

}