等待戈多 （最短路板子题）

解题思路:

准备蓝桥杯了，这个网站很久也没上了，比赛没打过，这次来热热身

身为比赛第一题，最短路板子题目，只需要把平时 路径长度 换成 时间， 最后其实求的就是时间的最短路

注意事项:

水题，没注意的emm

注意一下 double变量吧

参考代码:

#pragma comment(linker, "/STACK:1024000000, 1024000000")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n,k;

int l[550][550];

double tim[550][550];

double lowcost[550];

bool vis[550];

void Dijkstra(int beg) {

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

        lowcost[i] = 5000000.0; vis[i] = false;

    }

    lowcost[beg] = 0;

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

        int k = -1;

        double Min = 5000000.0;

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

            if(!vis[i] && lowcost[i] < Min) {

                Min = lowcost[i];

                k = i;

            }

        }

        if(k == -1) break;

        vis[k] = true;

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

        if(!vis[i] && lowcost[k]+tim[k][i] < lowcost[i]) {

            lowcost[i]  = lowcost[k]+tim[k][i];

        }

    }

}

int main()

{

    //freopen("in.txt","r",stdin);

    scanf("%d%d",&n,&k);

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

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

            scanf("%d",&l[i][j]);

        }

    }

    int tmp;

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

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

            scanf("%d",&tmp);

            if(tmp != 0) tim[i][j] = l[i][j]*1.0/tmp;

            else tim[i][j] = 0;

        }

    }

    Dijkstra(1);    //其实主要是这部，上面都是处理

    printf("%.2f\n",lowcost[k]);

    return 0;

}