HDOJ－2066－一个人的旅行

Problem Description
虽然草儿是个路痴（就是在杭电待了一年多，居然还会在校园里迷路的人，汗~),但是草儿仍然很喜欢旅行，因为在旅途中 会遇见很多人（白马王子，^0^），很多事，还能丰富自己的阅历，还可以看美丽的风景……草儿想去很多地方，她想要去东京铁塔看夜景，去威尼斯看电影，去阳明山上看海芋，去纽约纯粹看雪景，去巴黎喝咖啡写信，去北京探望孟姜女……眼看寒假就快到了，这么一大段时间，可不能浪费啊，一定要给自己好好的放个假，可是也不能荒废了训练啊，所以草儿决定在要在最短的时间去一个自己想去的地方！因为草儿的家在一个小镇上，没有火车经过，所以她只能去邻近的城市坐火车（好可怜啊~）。

Input
输入数据有多组，每组的第一行是三个整数T，S和D，表示有T条路，和草儿家相邻的城市的有S个，草儿想去的地方有D个；
接着有T行，每行有三个整数a，b，time,表示a,b城市之间的车程是time小时；(1=<(a,b)<=1000;a,b 之间可能有多条路)
接着的第T+1行有S个数，表示和草儿家相连的城市；
接着的第T+2行有D个数，表示草儿想去地方。

Output
输出草儿能去某个喜欢的城市的最短时间。

Sample Input
6 2 3
1 3 5
1 4 7
2 8 12
3 8 4
4 9 12
9 10 2
1 2
8 9 10

Sample Output
9

题比较直观，即单源求最短路，可以用spfa算法，也可以用floyd算法。

sofa：

#include<stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXSIZE 1000
#define INF 0x3f3f3f3f //表示无穷大
//#define MAX(a, b) a > b ? a : b
//#define MIN(a, b) a < b ? a : b
typedef void Status;
typedef int QElemType;

struct node
{
    int from;
    int to;
    int time;
    int next;
} edge[10 * MAXSIZE];

int head[MAXSIZE];
int vis[MAXSIZE];
int map[MAXSIZE];
int b[MAXSIZE];
int e[MAXSIZE];
int edgeNum, T;

//循环队列顺序存储结构
typedef struct
{
    QElemType data[MAXSIZE];
    int front;  //头指针
    int reat;   //尾指针，若队列不空，指向队列尾元素的下一个位置
} SqQueue;

//初始化一个空队列
Status InitQueue(SqQueue *Q)
{
    Q->front = 0;
    Q->reat = 0;
    return ;
}

//返回Q的元素个数，也就是队列当前长度
int QueueLength(SqQueue Q)
{
    return (Q.reat - Q.front + MAXSIZE) % MAXSIZE;
}

//若队列未满，则插入元素e为Q新队尾元素
Status EnQueue(SqQueue *Q, QElemType e)
{
    if ((Q->reat + 1) % MAXSIZE == Q->front)
    {
        return ;
    }

    Q->data[Q->reat] = e;
    Q->reat = (Q->reat + 1) % MAXSIZE;
    return ;
}

//若队列不空，则删除Q中队头元素
Status DeQueue(SqQueue *Q)
{
    if (Q->front == Q->reat)
    {
        return ;
    }
    Q->front = (Q->front + 1) % MAXSIZE;
    return ;
}

void init()
{
    //初始化为-1
    memset(map, -1, sizeof(map));

    edgeNum = 0;
    return ;
}

void add(int a, int b, int time)
{
    struct node E = {a, b, time, head[a]};
    edge[edgeNum] = E;
    head[a] = edgeNum++;
    return ;
}

//佛洛依德算法，最短路
void spfa(int neiCity)
{
    SqQueue Q;
    InitQueue(&Q);
    memset(vis, 0, sizeof(vis));
    memset(map, 0x3f, sizeof(map));

    vis[neiCity] = 1;
    map[neiCity] = 0;

    EnQueue(&Q, neiCity);

    while (QueueLength(Q))
    {
        int u = Q.front, i;
        DeQueue(&Q);
        vis[u] = 0;
        for (i = head[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].to;
            if (map[v] > map[u] + edge[i].time)
            {
                map[v] = map[u] + edge[i].time;
                if (!vis[v])
                {
                    vis[v] = 1;
                    EnQueue(&Q, v);
                }
            }
        }
    }
    return ;
}

int main()
{
    int T, S, D;
    int a, b, time;
    int neiCity[MAXSIZE], goCity[MAXSIZE];
    int i, j, min;
    while (~scanf("%d %d %d", &T, &S, &D))
    {
        init();

        while (T--)
        {
            scanf("%d %d %d", &a, &b, &time);

            add(a, b, time);
            add(b, a, time);    //双向图
        }

        for (i = 0; i < S; i++)
        {
            scanf("%d", neiCity + i);
        }

        for (i = 0; i < D; i++)
        {
            scanf("%d", goCity + i);
        }

        min = INF;

        for (i = 0; i < S; i++)
        {
            spfa(neiCity[i]);
            for (j = 0; j < D; j++)
            {
                if (min > map[goCity[j]])
                {
                    min = map[goCity[j]];
                }
            }
        }
        printf("%d\n", min);
    }
    return 0;
}

floyd：

#include<stdio.h>
#include <string.h>
#define MAXSIZE 1000
#define INF 0x3f3f3f3f //表示无穷大
#define MAX(a, b) a > b ? a : b
#define MIN(a, b) a < b ? a : b

int map[MAXSIZE][MAXSIZE];

void init()
{
    //初始化为无穷大
    memset(map, 0x3f, sizeof(map));

    for (int i = 1; i < MAXSIZE; i++)
    {
        map[i][i] = 0;
    }

    return ;
}

//佛洛依德算法，最短路
void floyd(int n)
{
    int i, j, k;
    for (k = 1; k <= n; k++)
    {
        for (i = 1; i <= n; i++)
        {
            if (map[i][k] != INF)
            {
                for (j = 1; j <= n; j++)
                {
                    map[i][j] = MIN(map[i][j], map[i][k] + map[k][j]);
                }
            }
        }
    }
    return ;
}

int main()
{
    int T, S, D;
    int a, b, time;
    int neiCity[MAXSIZE], goCity[MAXSIZE];
    int i, j, n, min;
    while (~scanf("%d %d %d", &T, &S, &D))
    {
        init();
        n = -1;

        while (T--)
        {
            scanf("%d %d %d", &a, &b, &time);

            if (map[a][b] > time)
            {
                map[a][b] = map[b][a] = time;
            }

            n = MAX(MAX(n, a), b);
        }

        for (i = 0; i < S; i++)
        {
            scanf("%d", neiCity + i);
        }

        for (i = 0; i < D; i++)
        {
            scanf("%d", goCity + i);
        }

        floyd(n);

        min = INF;

        for (i = 0; i < S; i++)
        {
            for (j = 0; j < D; j++)
            {
                min = MIN(min, map[i][goCity[j]]);
            }
        }

        printf("%d\n", min);
    }
    return 0;
}

如果用C写的话，建议用第二种，毕竟第一种需要用到队列，而队列需要自己去实现。好处是，自己写的队列可以进行优化，将不必要的功能删去。