boj 1291 无线新时代 bfs求两点间最短路

无线新时代Submit: 223   Accepted:67Time Limit: 1000MS  Memory Limit: 65536KDescription
古老的原始部 落ACElite的居民们一直过着日出而做，日落而出的简单生活。酋长dalong为了改善大家的生活，研究出了一种新的无线通讯工具，便于大家之间相互 交流。这需要架设多个基站进行通信。但由于各种原因，他无法保证这项技术是否成功，所以决定和champ测试一下。
现在我们知道ACElite部落有n（n<=10000）个山头，每个山头都可以架设基站。但如果山头间的距离大于c，基站间便无法通信。
在测试时dalong在s山头，champ在t山头，他们需要架设一些基站以进行通信。于是dalong希望YesXdogdog购买一些材料来架设基 站，为了节约资源，YesXdogdog希望如果dalong和champ能通信的情况下架设的基站尽可能的少。当然，如果不能通信，他也没办法了。你能 帮助YesXdogdog解决这个问题吗？

Input
单组数据测试
输入的第一行为3个数，n，m，c。表示ACElite部落有n(n<=10000)个山头，m(m<=100000)表示有m条边，c表示 两个基站通信的最大距离。
后面有m行，每行3个数a,b,l，表示a，b（1<=a,b<=n）山头之间可以架设基站且它们的距离为l。
最后一行为两个数 s，t表示dalong和champ的位置

Output
一个数，最少需要架设的基站。
如果无法通信，输出Impossible


Sample Input

4 4 10
1 2 3
2 3 9
1 4 8
1 3 11
1 3

Sample Output

3

Hint
巨大的输入输出，推荐printf,scanf


dijkstral超时,m值太大

#include <stdio.h>
#include <bitset>
using namespace std;

#define MAX_INT 0x7fffffff

bitset<100100010> path;
int map[10010], processed[10010];

void init_single_source(int *map, int size, int source)
{
    int i;
    for (i=1 ; i<=size ; i++)
        map[i] = MAX_INT;
    map[source] = 0;
}

int extract_min(int *map, int size)
{
    int i, min, min_index;
    min = MAX_INT;
    for (i=1 ; i<=size ; i++)
    {
        if (map[i] < min && 0 == processed[i])
        {
            min = map[i];
            min_index = i;
        }
    }
    if (min == MAX_INT)
        return -1;
    processed[min_index] = 1;
    return min_index;
}

int main(int argc, char *argv[])
{
    int n, m, c, a, b, l, s, t, i, min_index, j;
    scanf("%d %d %d", &n, &m, &c);
    for (i=0 ; i<m ; i++)
    {
        scanf("%d %d %d", &a, &b, &l);
        if (l > c)
            continue;
        path.set(a * n + b);
    }
    init_single_source(map, n, a);
    for (i=0 ; i<n ; i++)
    {
        min_index = extract_min(map, n);
        if (-1 == min_index)
        {
            printf("Impossible\n");
            return 0;
        }
        /* do release */
        for (j=1 ; j<=n ; j++)
        {
            if (!path.test(min_index * n + j))
                continue;
            if (map[j] > map[min_index] + 1)
            {
                map[j] = map[min_index] + 1;
            }
        }
    }
    /* print out min path */
    if (MAX_INT == map[b])
        printf("Impossible\n");
    else
        printf("%d\n", map[b] + 1);
}

换BFS过之。
BFS代码有一些需要注意的地方，详细见代码

#include <iostream>
#include <deque>
#include <bitset>
#include <vector>
using namespace std;

typedef struct _node
{
    int hill;
    int step;
}ST_NODE;

/* how to define double diamond vector */
vector<int> array[10001];
int visited[10001]; /*标记某点是否已访问，已访问的点不在处理*/

int bfs(int size, int source, int dest)
{
    int hill, i, next_step, step;
    vector<int>::iterator iter;
    vector<int>::iterator begin;
    vector<int>::iterator end;

    ST_NODE node;
    deque<ST_NODE> deq_index;
    node.hill = source;
    node.step = 1;
    deq_index.push_back(node);
    visited[source] = 1;
    while (!deq_index.empty())
    {
        node = deq_index.front();
        deq_index.pop_front();
        hill = node.hill;
        step = node.step;
        begin = array[hill].begin();
        end = array[hill].end();
        for (iter = begin ; iter != end ; iter++)
        {
            if (dest == *iter)
                return step;
            if (visited[*iter] == 0) /*这里注意检查点是否已访问，否则会出现程序无法结束的情况*/
            {
                next_step = step + 1;/*这里计算步长，而不是距离*/
                node.hill = *iter;
                node.step = next_step;
                deq_index.push_back(node);
                visited[*iter] = 1;
            }
        }
    }
    return 0;
}

int main(int argc, char *argv[])
{
    int n, m, c, a, b, l, s, t, i, steps;
    scanf("%d %d %d", &n, &m, &c);
    for (i=0 ; i<m ; i++)
    {
        scanf("%d %d %d", &a, &b, &l);
        if (l > c)
            continue;
        array[a].push_back(b);/*注意是无向图*/
        array[b].push_back(a);
    }
    cin >> s >> t;
    steps = bfs(n, s, t);
    if (0 == steps)
        printf("Impossible\n");
    else
        printf("%d\n", steps + 1);
}