Hdu-2066 一个人的旅行

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2066

解题思路：

很裸的单源最短路Dijkstra算法。只不过起点给你多个，然后求可以到达的目的地中路径最短的一条。

两层for循环筛选出即可。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
#define MAX 0x3f3f3f3f
int road, link, want, total;
int map[1010][1010], linkarr[1010], wantarr[1010], dis[1010];
bool visit[1010];

void Dijkstra(int start)
{
    int temp, k;
    memset(visit, 0, sizeof(visit));
    for(int i = 1; i <= total; ++i)
        dis[i] = map[start][i];
    dis[start] = 0;
    visit[start] = 1;
    for(int i = 1; i <= total; ++i)
    {
        temp = MAX;
        for(int j = 1; j <= total; ++j)
            if(!visit[j] && temp > dis[j])
                temp = dis[k = j];
        visit[k] = 1;
        for(int j = 1; j <= total; ++j)
            if(!visit[j] && dis[j] > dis[k] + map[k][j])
                dis[j] = dis[k] + map[k][j];
    }
}

int main()
{
    int x, y, cost, minn, answer;
    while(scanf("%d%d%d", &road, &link, &want) != EOF)
    {
        total = 0;
        memset(map, MAX, sizeof(map));
        for(int i = 1; i <= road; ++i)
        {
            scanf("%d%d%d", &x, &y, &cost);
            if(cost < map[x][y])
                map[x][y] = map[y][x] = cost;
            total = max(total, max(x, y)); //错了N久。。。。因为没有给出点的个数。
        }
        for(int i = 1; i <= link; ++i) //相连的城市
            scanf("%d", &linkarr[i]);
        for(int i = 1; i <= want; ++i) //目的地
            scanf("%d", &wantarr[i]);
        answer = MAX;
        for(int i = 1; i <= link; ++i) //linkarr数组中所有元素中到达目的地最短的路
        {
            Dijkstra(linkarr[i]);
            minn = MAX;
            for(int j = 1; j <= want; ++j) //linkarr[i]中可以到达的目的地中最短
                if(dis[wantarr[j]] < minn)
                    minn = dis[wantarr[j]];
            if(answer > minn)
                answer = minn;
        }
        printf("%d\n", answer);
    }
    return 0;
}