程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Lift Hopping (Uva 10801 最短路)

Lift Hopping (Uva 10801 最短路)

編輯：C++入門知識

Lift Hopping (Uva 10801 最短路)

題意：n個電梯，100層樓，告訴每個電梯的速度和每個電梯會停的樓層數，起點在0層，終點是第k層，另外每次換乘需要等待60秒，問從0到k的最短時間是多少。

思路：這題就是讀入比較蛋疼，然後根據輸入建完圖後跑一下Dijkstra。在更新時加入60秒。

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#pragma comment (linker,/STACK:102400000,102400000)
#define pi acos(-1.0)
#define eps 1e-6
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define FRE(i,a,b)  for(i = a; i <= b; i++)
#define FREE(i,a,b) for(i = a; i >= b; i--)
#define FRL(i,a,b)  for(i = a; i < b; i++)
#define FRLL(i,a,b) for(i = a; i > b; i--)
#define mem(t, v)   memset ((t) , v, sizeof(t))
#define sf(n)       scanf(%d, &n)
#define sff(a,b)    scanf(%d %d, &a, &b)
#define sfff(a,b,c) scanf(%d %d %d, &a, &b, &c)
#define pf          printf
#define DBG         pf(Hi
)
typedef long long ll;
using namespace std;

#define INF 0x3f3f3f3f
#define mod 1000000009
const int maxn = 105;
const int MAXN = 3005;
const int MAXM = 200010;
const int N = 1005;

int mp[maxn][maxn],TIME[6];
int dist[maxn];
bool vis[maxn];
int n,k;
char str[MAXN];
int a[maxn];

int readLine(char *s)
{
    int L;
    for (L=0;(s[L]=getchar())!='
'&&s[L]!=EOF;L++) ;
    s[L]=0;
    return L;
}

void Dijkstra()
{
    int i,j,now,mi;
    mem(dist,INF);
    mem(vis,false);
    for (i=0;i<100;i++)
        dist[i]=mp[0][i];
    dist[0]=0;
    vis[0]=true;
    for (i=0;i<100;i++)
    {
        now=-1;
        mi=INF;
        for (j=0;j<100;j++)
        {
            if (!vis[j]&&mi>dist[j])
            {
                now=j;
                mi=dist[j];
            }
        }
//        printf(now=%d
,now);
        if (now==-1) break;
//        DBG;
        vis[now]=true;
        for (j=0;j<100;j++)
        {
            if (!vis[j]&&dist[j]>dist[now]+mp[now][j]+60)
                dist[j]=dist[now]+mp[now][j]+60;
        }
    }
//    for (i=0;i<=30;i++)
//        pf(%d ,dist[i]);
    if (dist[k]>=INF)
        pf(IMPOSSIBLE
);
    else
        pf(%d
,dist[k]);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen(C:/Users/lyf/Desktop/IN.txt,r,stdin);
#endif
    int i,j;
    while (~sff(n,k))
    {
        mem(mp,INF);
        for (i=0;i