[HDU 1548]A Strange Lift[Dijkstra最短路]

题意:

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

思路:

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

注意:

vector要清空 ! ! ! [ 泪目]

#include   
#include   
#include   
using namespace std; 
const int MAXN = 205; 
const int INF = 0x3f3f3f3f; 
vector 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;id[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)); 
    } 
} 

#include 
#include 
#include 
using namespace std;
const int MAXN = 205;
const int INF = 0x3f3f3f3f;
vector 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;id[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   
#include   
#include   
#include   
#include   
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 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 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