学步园

题意:

电梯, 在第 i 层只能向上或向下走 ki 步, 问从 A 层到 B 层最少走多少步.

思路:

有向图求最短路. 用Dijkstra, 都是正权值.

注意:

vector要清空 ! ! !  [ 泪目]

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 205;
const int INF = 0x3f3f3f3f;
vector<int> edge[MAXN];
int n,d[MAXN];
bool vis[MAXN];

int Dijkstra(int s, int t)//加了许多特判..
{
    if(t>n||s>n) return -1;
    if(t==s)    return 0;
    memset(d,0x3f,sizeof(d));
    memset(vis,false,sizeof(vis));
    d[s] = 0;
    for(int i=0;i<n;i++)
    {
        int k = 0, mi = INF;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j] && d[j]<mi)
            {
                mi = d[j];
                k = j;
            }
        }
        if(k==0)    return -1;
        if(k==t)    return mi;
        vis[k] = true;
        for(int j=0,v;j<edge[k].size();j++)
        {
            v = edge[k][j];
            if(!vis[v] && d[v]>d[k]+1)
                d[v] = d[k] + 1;
        }
    }
}

int main()
{
    while(scanf("%d",&n) && n)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        for(int i=1;i<=n;i++)
        {
            int k,up,down;
            scanf("%d",&k);
            edge[i].clear();///坑啊~~~为什么codeblocks调试的时候没异常呢 > <
            if(!k)  continue;
            if((up = i+k)<=n)
                edge[i].push_back(up);
            if((down = i-k)>=1)
                edge[i].push_back(down);
        }
        printf("%d\n",Dijkstra(a,b));
    }
}

另附Dijkstra模板:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
#define N 1002
#define inf 0x3f3f3f3f
struct node {
    int v, w;
    node() {}
    node(int _v, int _w):v(_v), w(_w) {}
};
vector<node> g[N];
int n, m, d[N];
bool vis[N];

int Dijkstra(int s, int t) {
    memset(d, 0x3f, sizeof(d));
    memset(vis, false, sizeof(vis));
    d[s] = 0;
    for (int i=0; i<n; i++) {
        int k = 0, mi = inf;
        for (int j=1; j<=n; j++) 
            if (!vis[j] && d[j] < mi)
            {    mi = d[j], k = j;}
        if (k == 0) break;
        vis[k] = true;
        for (int j=0, v, w; j<g[k].size(); j++) {
            v = g[k][j].v, w = g[k][j].w;
            if (!vis[v] && d[v] > d[k] + w)
                d[v] = d[k] + w;
        }
    }
    return d[t];
}
int main() {
    while (scanf("%d%d", &n, &m) == 2) {
        for (int i=0; i<=n; i++) g[i].clear();
        for (int i=0, a, b, c; i<m; i++) {
            scanf("%d%d%d", &a, &b, &c);
            g[a].push_back(node(b, c));
            g[b].push_back(node(a, c));
        }
        int s, t;
        scanf("%d%d", &s, &t);
        printf("%d\n", Dijkstra(s, t));
    }


    return 0;
}

[ 附 ]
菜鸟好去处:

http://www.nocow.cn/index.php/Dijkstra%E7%AE%97%E6%B3%95