時(shí)間限制: 1Sec 內(nèi)存限制: 128MB 提交: 264 解決: 19

題目描述
戈多是一個(gè)普通的小盆友，他居住在1城市。小x在k城等待戈多。

可惜戈多有點(diǎn)奇怪，在城市之間的道路上，他的速度有時(shí)快有時(shí)慢。

現(xiàn)在小x想知道，戈多最快到達(dá)的時(shí)間是多少？

輸入
第一行是兩個(gè)數(shù)字n(n<=500)，k，表示城市的個(gè)數(shù)和小x的位置。

接下來(lái)是一個(gè)正整數(shù)的矩陣l，第i行第j列表示i到j(luò)的路徑長(zhǎng)度。

接下來(lái)是一個(gè)正整數(shù)的矩陣v，表示戈多從i到j(luò)路徑所走的速度。

輸出
輸出一個(gè)浮點(diǎn)數(shù)，表示戈多最快到達(dá)的時(shí)間，保留兩位小數(shù)
樣例輸入
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
提示
無(wú)

#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;
}