nyoj 115 城市平乱（图的Dijkstra算法+堆优化）

该题网址：http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=115

描述

南将军统领着N个部队，这N个部队分别驻扎在N个不同的城市。

他在用这N个部队维护着M个城市的治安，这M个城市分别编号从1到M。

现在，小工军师告诉南将军，第K号城市发生了暴乱，南将军从各个部队都派遣了一个分队沿最近路去往暴乱城市平乱。

现在已知在任意两个城市之间的路行军所需的时间，你作为南将军麾下最厉害的程序员，请你编写一个程序来告诉南将军第一个分队到达叛乱城市所需的时间。

注意，两个城市之间可能不只一条路。

输入

第一行输入一个整数T，表示测试数据的组数。(T<20)

每组测试数据的第一行是四个整数N,M,P,Q(1<=N<=100,N<=M<=1000,M-1<=P<=100000)其中N表示部队数，M表示城市数，P表示城市之间的路的条数,Q表示发生暴乱的城市编号。

随后的一行是N个整数，表示部队所在城市的编号。

再之后的P行，每行有三个正整数，a,b,t(1<=a,b<=M,1<=t<=100)，表示a,b之间的路如果行军需要用时为t

数据保证暴乱的城市是可达的。

输出

对于每组测试数据，输出第一支部队到达叛乱城市时的时间。每组输出占一行

样例输入

1

3 8 9 8

1 2 3

1 2 1

2 3 2

1 4 2

2 5 3

3 6 2

4 7 1

5 7 3

5 8 2

6 8 2

样例输出

4

思路

以叛乱城市为起点，采用Dijkstra算法寻找最短的驻部队城市。关于Dijkstra算法，见https://blog.csdn.net/qq_35644234/article/details/60870719

注意：这道题在使用Dijkstra算法的时候不需要把起点到其他所有点的最短路径都求出来，只需找到叛乱城市对应的点到最短的一个部落之间的距离就可以结束Dijkstra算法。

因此可以使用set容器储存部落所在的城市编号，每次求出一个最短路径就判断该结点是否在部落编号集合中。同时Dijkstra算法还可以使用堆优化，使算法时间复杂度从O（n²）提高到O(nlogn)。

代码

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<limits>
#include<utility>
#include<list>
#include<set>
using namespace std;
const int inf = numeric_limits<int>::max();//int最大值
typedef pair<int, int>pii;//前者int表示路径长度，后者为城市编号
int nArmy, nCity, nRoad;
set<int>army;
vector<int>dist;//非负权值的单源最短路径
struct edge
{
    int to, cost;
    edge(int x,int y):to(x),cost(y){}
};
list<edge>city[];//图的邻接表储存
int dijkstra(int st)
{
    priority_queue<pii, vector<pii>, greater<pii> >qu;//优先级队列采用小顶堆
    dist.assign(nCity + , inf);
    dist[st] = ;
    list<edge>::iterator it ;
    pii tmp;
    int curr;//当前最短路径对应的编号
    qu.push(make_pair(dist[st], st));
    while (!qu.empty())
    {
        tmp = qu.top();//取得已得到最短路径长度
        qu.pop();
        curr = tmp.second;
        if (tmp.first != dist[curr])continue;//说明当前结点已经访问过.不需要再单独设置一个标记数组
        if (army.find(curr) != army.end())
            return dist[curr];
        //修改数据
        for (it = city[curr].begin(); it != city[curr].end(); it++)
        {
            if (it->cost + dist[curr] < dist[it->to])
            {
                dist[it->to] = it->cost + dist[curr];
                qu.push(make_pair(dist[it->to], it->to));
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie();
    int riot,T,i,v1,v2,cost,tmp;
    cin >> T;
    while (T--)
    {
        cin >> nArmy >> nCity >> nRoad >> riot;
        army.clear();
        for (i = ; i <= nCity; i++)city[i].clear();//city编号从1开始
        for (i = ; i < nArmy; i++)//army编号从0开始
        {
            cin >> tmp;
            army.insert(tmp);
        }
        for (i = ; i < nRoad; i++)
        {
            cin >> v1 >> v2 >> cost;
            city[v1].push_back(edge(v2, cost));
            city[v2].push_back(edge(v1, cost));
        }
        cout << dijkstra(riot) << endl;
    }
    return ;
}