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

題意:

電梯, 在第 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)); 
    } 
} 

#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; 
}