Frogger

最短路徑中的最大邊的最小值是多少?

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define INF 0x3f3f3f
using namespace std;
double dis[1100];
int vis[1100];
double x[1100],y[1100];
double mp[1100][1100];
int n;
void dijst(int x)
{
    memset(vis,0,sizeof(vis));
    int v;
    vis[x]=1;
    for(int i=1;i<=n;i++)
    {
        dis[i]=mp[x][i];//dis存儲的是第i個點到第1個點的距離中的最大距離的最小值
        //printf("%.3lf ",dis[i]);
    }
    //printf("\n");
    while(true)
    {
        v=-1;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]&&(v==-1||dis[v]>dis[i]))//找出最小的邊
            {
                v=i;
            }
        }
        if(v==-1)
        {
            break;
        }
        vis[v]=1;
        for(int i=1;i<=n;i++)
        {
            dis[i]=min(dis[i],max(dis[v],mp[v][i]));//更新第i個點到第1個點的最大距離最小值（直達與轉(zhuǎn)車的比較）
            //printf("%.3lf ",dis[i]);
        }
        //printf("\n");
    }
}
int main( )
{
    int t=0;
    while(~scanf("%d",&n)&&n)
    {
        memset(mp,INF,sizeof(mp));
        memset(dis,INF,sizeof(dis));
        t++;
        for(int i=1;i<=n;i++)
        {
            scanf("%lf%lf",&x[i],&y[i]);
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                mp[i][j]=mp[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
                //mp存儲的的第i個點到第j個點的距離
            }
        }
        // for(int i=1;i<=n;i++)
        // {
        //     for(int j=1;j<=n;j++)
        //     {
        //         printf("%.3lf ",mp[i][j]);
        //     }
        //     cout<<endl;
        // }
        // cout<<endl;
        dijst(1);
        printf("Scenario #%d\nFrog Distance = %.3f\n\n",t,dis[2]);
    }
    return 0;
}

Heavy Transportation

最短路徑中最小邊的最大值可以是多少

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int M=1100;
int mp[M][M];
int vis[M];
int dis[M];
int n,m;
void dijst(int x)
{
    memset(vis,0,sizeof(vis));
    int v;
    vis[x]=1;
    for(int i=1;i<=n;i++)
    {
        dis[i]=mp[x][i];//dis儲存的是第i個點到第1個點的距離中最小距離的最大值
    }
    while(true)
    {
        v=-1;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]&&(v==-1||dis[v]<dis[i]))//找出最大邊
            {
                v=i;
            }
        }
        if(v==-1)
        {
            break;
        }
        vis[v]=1;
        for(int i=1;i<=n;i++)
        {
            dis[i]=max(dis[i],min(dis[v],mp[v][i]));
            //更新第i個點到第1個點的距離中的最小距離的最大值
        }
    }
}
int main( )
{
    int t,k=0,x,y,w;
    scanf("%d",&t);
    while(t--)
    {
        k++;
        memset(mp,-1,sizeof(mp));
        memset(dis,-1,sizeof(dis));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&w);
            mp[x][y]=mp[y][x]=w;
        }
        dijst(1);
        printf("Scenario #%d:\n%d\n\n",k,dis[n]);
    }
    return 0;
}