UVA 10801 多线程最短路

题意:一栋摩天大楼从0层到K层,有N部电梯,每个电梯都有自己的运行速度,此外,对于某个电梯来说,并不是每一层都会停,允许在某一层进行电梯换乘,每次换乘固定消耗60秒,最终求从0层去K层的最短时间,如果不能到达,输出 IMPOSSIBLE

确实是个隐式图问题,建图并不难,只要图建好了,进行最短路即可,难点在于电梯换乘,因为电梯换乘额外消耗60s因此,不能简单的指向该层节点,结果明显不对。。。。所以我自己就想出了一个多线程的最短路,每个电梯独立建一个图,分别以0-99,100-199,200-299.。。。因为最多有五部电梯,因此,只需要最多400-499一共500个点即可,独立图中点是指相同层数,只是百位不同,所以每个相同层的点互相建边,边权为60。

图建好后进行最短路即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 1<<30
using namespace std;
int g[510][510];
int times[10];
int lift[10][110];
int num[10];
int d[510];
int vis[510];
int n,k;
void init()
{
    int i,j;
    for (i=0;i<=509;i++)
    {
        for (j=0;j<=509;j++)
        {
            if (i==j) g[i][j]=0;
            else
                g[i][j]=INF;
        }
        d[i]=INF;
    }
    for (i=0;i<=99;i++)
    {
        for (j=0;j<n;j++)
        {
            for (int w=0;w<n;w++) //把不同电梯的相同层的节点进行连接,权值为60,代表换乘电梯
            {
                if (w==j) continue;
                g[j*100+i][w*100+i]=60;
            }
        }
    }

}
void dijstla()
{
    d[500]=0;
    int i,j;
    memset(vis,0,sizeof vis);
    for (i=0;i<=500;i++)
    {
        int mini=INF,loc;
        for (j=0;j<=500;j++)
        {
            if (vis[j]) continue;
            if (mini>d[j])
            {
                mini=d[j];
                loc=j;
            }
        }
        vis[loc]=1;
        for (j=0;j<=500;j++)
        {
            if (vis[j]) continue;
            if (loc==j) continue;
            if (g[loc][j]>=INF) continue;
            if (d[j]>d[loc]+g[loc][j])
                d[j]=d[loc]+g[loc][j];
        }
    }
}
int main()
{
    int i,j;
    while (scanf("%d%d",&n,&k)!=EOF)
    {
        for (i=0;i<n;i++)
        {
            scanf("%d",&times[i]);
        }
        for (i=0;i<n;i++)
        {
            int cur=0;
            char ch;
            while (1){
             scanf("%d",&lift[i][cur++]);
             ch=getchar();
             if (ch=='
') break;
            }
            num[i]=cur;
            sort(lift[i],lift[i]+cur);
        }
        init();
        for (i=0;i<n;i++)
        {
            for (j=0;j<num[i];j++)
            {
                for (int w=j+1;w<num[i];w++)
                {
                    int t1=100*i+lift[i][j];
                    int t2=100*i+lift[i][w];
                    g[t1][t2]=g[t2][t1]=(t2-t1)*times[i]; //分别给每个电梯建图
                }
            }
        }
        for (i=0;i<n;i++)
        {
            if (lift[i][0]==0) g[500][i*100]=0;//为防止0层有多个电梯可达,因此添加500为一个超级原点,500到各0层点权值均为0
        }
        dijstla();
        int ans=INF;
        for (i=0;i<n;i++)
        {
            if (ans>d[i*100+k])
                ans=d[i*100+k];
        }
        if (ans>=INF) puts("IMPOSSIBLE");
        else printf("%d
",ans);
    }
    return 0;
}
原文地址:https://www.cnblogs.com/kkrisen/p/3517949.html