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 ;
}