时间限制: 1Sec 内存限制: 128MB 提交: 264 解决: 19

题目描述
戈多是一个普通的小盆友，他居住在1城市。小x在k城等待戈多。

可惜戈多有点奇怪，在城市之间的道路上，他的速度有时快有时慢。

现在小x想知道，戈多最快到达的时间是多少？

输入
第一行是两个数字n(n<=500)，k，表示城市的个数和小x的位置。

接下来是一个正整数的矩阵l，第i行第j列表示i到j的路径长度。

接下来是一个正整数的矩阵v，表示戈多从i到j路径所走的速度。

输出
输出一个浮点数，表示戈多最快到达的时间，保留两位小数
样例输入
6 3
0 5 3 6 2 4
5 0 1 7 10 3
3 1 0 8 9 4
6 7 8 0 2 6
2 10 9 2 0 5
4 3 4 6 5 0
0 1 4 5 6 3
1 0 5 7 9 6
4 5 0 3 2 4
5 7 3 0 1 1
6 9 2 1 0 8
3 6 4 1 8 0
样例输出
0.75
提示
无

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=510;
double G[maxn][maxn];
bool vis[maxn];
int pre[maxn];
double d[maxn];
int n,k;
double INF=0x7FFFFFFF;
void dijkstra(int s)
{
    for(int i=1;i<=n;i++) d[i]=INF,pre[i]=i;
    d[s]=0;
    for(int i=1;i<=n;i++)
    {
        int u=-1,MIN=INF;
        for(int j=1;j<=n;j++)
        {
            if(vis[j]==false && d[j]<MIN)
            {
                u=j;
                MIN=d[j];
            }
        }
        if(u==-1) return ;
        vis[u]=true;
        for(int v=1;v<=n;v++)
        {
            if(vis[v]==false && G[u][v]!=INF &&  d[u]+G[u][v]<d[v])
            {
                d[v]=d[u]+G[u][v];
                pre[v]=u;
            }
        }
    }
}
int main(void)
{
    //freopen("D:\\input1.txt","r",stdin);
    while(cin>>n>>k)
    {
        fill(vis,vis+maxn,0);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                cin>>G[i][j];
            }
        }
        
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                double v;
                cin>>v;
                if(i!=j && v!=0)
                {
                    G[i][j]=G[i][j]/v;
                }
                else 
                {
                    G[i][j]=INF;    
                } 
            }
        }
        dijkstra(1);
        printf("%.2lf",d[k]);
    }
    return 0;
}