昨天刚总结完最短路，今天刷题的时候就遇到了最短路问题，本以为轻轻松松，但没想到到处是坑。

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

题意：

中文题，题意不再描述。

分析：

把小女孩家当作起点0，附近与之相邻的城市也在最短路中，且权值设为0，然后跑一边dijkstra.

注意：

题目中有重边，且顶点不一定连续。比如a->b有权值为2的边，b->a可以有权值为3的边。

我使用的是邻接表+优先队列优化过的dijkstra

#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1010;

struct edge{
    int to, cost;   // to是到达的点，cost是对应的权值
};
typedef pair<int, int> P;   // first是最小权值，second是顶点编号
vector<edge> G[N];
int dis[N];

int t, s, d;

void djk(int s)
{
    priority_queue<P, vector<P>, greater<P> > q;    // 优先队列，权值越小优先级越高
    for(int i=0; i<N; i++)  // 初始化
        dis[i] = INF;
    dis[s] = 0;
    
    q.push(P(0, s));    // 把起点放入队列中
    while(!q.empty())
    {
        P p = q.top();  q.pop();
        int v = p.second;
        if(dis[v] < p.first)    continue;
        for(int i=0; i<G[v].size(); i++)    // 遍历当前顶点所能到达的所有顶点
        {
            edge e = G[v][i];
            if(dis[e.to] > dis[v] + e.cost) // 如果到下一个点的距离大于通过当前这个点到下一个点的距离，就更新下一个点的最小距离
            {
                dis[e.to] = dis[v] + e.cost;
                q.push(P(dis[e.to], e.to)); // 更新后放入队列中
            }
        }
    }
}

int maps[N][N]; // 用于辅助的邻接矩阵，方便去掉重边

int main()
{
    while(scanf("%d %d %d", &t, &s, &d) != EOF)
    {
        for(int i=0; i<N; i++)  G[i].clear();
        
        int a;
        edge b;

        for(int i=0; i<N; i++)  
            for(int j=0; j<N; j++)
                maps[i][j] = INF;
        
        for(int i=0; i<t; i++)
        {
            scanf("%d %d %d", &a, &b.to, &b.cost);
            // G[a].push_back(b);   
            // a可能到b，b也可能到a，而且权值可能不一样
            maps[a][b.to] = maps[b.to][a] = min(min(maps[a][b.to], maps[b.to][a]), b.cost); // 去重边
        }

        for(int i=0; i<N; i++)  // 把边从邻接矩阵中读入邻接表
        {
            for(int j=0; j<N; j++)
            {
                if(maps[i][j] != INF)
                {
                    b.to = j;
                    b.cost = maps[i][j];
                    G[i].push_back(b);
                }
            }
        }


        for(int i=0; i<s; i++)
        {
            scanf("%d", &b.to);
            b.cost = 0;
            G[0].push_back(b);
        }
        djk(0);
        int ans = INF;
        for(int i=0; i<d; i++)
        {
            scanf("%d", &a);
            ans = min(ans, dis[a]);
        }
        printf("%d\n", ans);
    }

    return 0;
}