HDU 1548 - A strange lift

传送门

HDU 1548 - A strange lift

题意

有个电梯,每层只能上下固定的层数,求到达目的地最小的换乘次数

思路

建图就行。

不过Floyd死活过不去(°∀°)ノ

代码

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define LL long long
const int MAXN = 200 + 5;
const int INF = 0x3f3f3f3f;
 
int mp[MAXN][MAXN], n, d[MAXN];
typedef pair<int, int> pii;
priority_queue<pii, vector<pii>, greater<pii> > qu;
 
void Dijkstra(int st)
{
    memset(d, 0x3f, sizeof d);
    d[st] = 0;
    qu.push(make_pair(d[st], st));
    while (!qu.empty())
    {
        pii u = qu.top();
        qu.pop();
        int x = u.second;
        if (d[x] != u.first)
            continue;
        for (int v = 1; v <= n; v++)
            if (d[v] > d[x] + mp[x][v])
            {
                d[v] = d[x] + mp[x][v];
                qu.push(make_pair(d[v], v));
            }
    }
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int st, ed, i, j;
    while (scanf("%d", &n), n)
    {
        scanf("%d%d", &st, &ed);
        int k = 0;
        for (i = 1; i <= n; i++)
            for (j = 1; j <= n; j++)
                mp[i][j] = (i == j ? 0 : INF);
        int t;
        for (i = 1; i <= n; i++)
        {
            scanf("%d", &t);
            if (i + t <= n)
                mp[i][i + t] = 1;
            if (i - t >= 1)
                mp[i][i - t] = 1;
        }
        Dijkstra(st);
        printf("%d\n", d[ed] == INF ? -1 : d[ed]);
    }
    return 0;
}

Powered by Jekyll and Theme by solid