hdu 1596 find the safest road(最短路求最大值的题目，有两种稍微不同的处理方式)-白红宇

hdu 1596 find the safest road(最短路求最大值的题目，有两种稍微不同的处理方式)

阅读量：4035 次

发布时间：2019-05-24

本文共 4631 字，大约阅读时间需要 15 分钟。

帮同学调个程序，一看题目不难，自己就试着做了一下，最短路的题目，稍微变换一点，就弱弱的错了n遍，太纠结了，写篇博客纪念一下这迟迟到来的AC。。。

1、

2、题目分析

其实这道题目就是简单地dijkstra，原来的加法得换成乘法，初始值也有所变化，就这么弱弱的错了n遍

AC代码：

#include
   
    #include
    
     #include
     
      using namespace std;#define N 1015double map[N][N];double dist[N];int vis[N];void dijstra(int v,int n){    //memset(dist,-1,sizeof(dist));    for(int i=1; i<=n; i++)        dist[i]=0;    for(int i=1; i<=n; i++)    {        //dist[i]=map[v][i];        vis[i]=0;    }    vis[v]=1;    dist[v]=1;    for(int ii=1; ii<=n; ii++)    {        double minn=0;        int u=v;        for(int i=1; i<=n; i++)        {            if(dist[i]>minn && vis[i]==0)            {                minn=dist[i];                u=i;            }        }        vis[u]=1;        for(int i=1; i<=n; i++)        {            if( vis[i]==0 )            {                double newdist=dist[u]*map[u][i];                if(newdist>dist[i])                    dist[i]=newdist;            }        }    }}int main(){    int n,Q,s,e;    while(scanf("%d",&n)!=EOF)    {        for(int i=1; i<=n; i++)        {            for(int j=1; j<=n; j++)            {                scanf("%lf",&map[i][j]);                //if(map[i][j]==0)                    //map[i][j]=INF;                //printf("%.3f ",map[i][j]);            }        }        scanf("%d",&Q);        while(Q--)        {            scanf("%d%d",&s,&e);            dijstra(s,n);            if(dist[e])            {                printf("%.3f\n",dist[e]);            }            else                printf("What a pity!\n");        }    }    return 0;}

另一种处理方式，如不注意vis[v]=1，这样赋值了，就会run time error

改正后的AC代码：

#include
   
    #include
    
     #include
     
      using namespace std;#define N 1015double map[N][N];double dist[N];int vis[N];void dijstra(int v,int n){    //memset(dist,-1,sizeof(dist));    for(int i=1; i<=n; i++)        dist[i]=0;    for(int i=1; i<=n; i++)    {        dist[i]=map[v][i];        vis[i]=0;    }    //标记了vis[v]=1，就会越界    //vis[v]=1;    //初始值是0表示无法到达，所以初始值是1    dist[v]=1;    for(int ii=1; ii<=n; ii++)    {        double minn=0;        int u;        for(int i=1; i<=n; i++)        {            if(dist[i]>minn && vis[i]==0)            {                minn=dist[i];                u=i;            }        }        vis[u]=1;        for(int i=1; i<=n; i++)        {            if( vis[i]==0 )            {                double newdist=dist[u]*map[u][i];                if(newdist>dist[i])                    dist[i]=newdist;            }        }    }}int main(){    int n,Q,s,e;    while(scanf("%d",&n)!=EOF)    {        for(int i=1; i<=n; i++)        {            for(int j=1; j<=n; j++)            {                scanf("%lf",&map[i][j]);                //if(map[i][j]==0)                    //map[i][j]=INF;                //printf("%.3f ",map[i][j]);            }        }        scanf("%d",&Q);        while(Q--)        {            scanf("%d%d",&s,&e);            dijstra(s,n);            if(dist[e])            {                printf("%.3f\n",dist[e]);            }            else                printf("What a pity!\n");        }    }    return 0;}

vis[v]可以标记成1，越界是u导致的

附AC代码：

#include
   
    #include
    
     #include
     
      using namespace std;#define N 4015double map[N][N];double dist[N];int vis[N];void dijstra(int v,int n){    //memset(dist,-1,sizeof(dist));    for(int i=1; i<=n; i++)        dist[i]=0;    for(int i=1; i<=n; i++)    {        dist[i]=map[v][i];        vis[i]=0;    }    vis[v]=1;    //初始值是0表示无法到达，所以初始值是1    dist[v]=1;    for(int ii=1; ii
      
       minn && vis[i]==0)            {                minn=dist[i];                u=i;            }        }        //printf("u=%d\n",u);        //得判断minn的值，如果找不到minn,那么u就会是任意值，可能越界        if(minn==0)        break;        vis[u]=1;        for(int i=1; i<=n; i++)        {            if( vis[i]==0 )            {                double newdist=dist[u]*map[u][i];                if(newdist>dist[i])                    dist[i]=newdist;            }        }    }}int main(){    int n,Q,s,e;    while(scanf("%d",&n)!=EOF)    {        for(int i=1; i<=n; i++)        {            for(int j=1; j<=n; j++)            {                scanf("%lf",&map[i][j]);                //if(map[i][j]==0)                    //map[i][j]=INF;                //printf("%.3f ",map[i][j]);            }        }        scanf("%d",&Q);        while(Q--)        {            scanf("%d%d",&s,&e);            dijstra(s,n);            if(dist[e])            {                printf("%.3f\n",dist[e]);            }            else                printf("What a pity!\n");        }    }    return 0;}