HDOJ 2066 （多源多汇最短路）

http://acm.hdu.edu.cn/showproblem.php?pid=2066

题意：
最短路问题，有多个源头和多个去向。
解法是把全部的源点压缩成一个点，再跑最短路。

Hint：

• 每次输入数据，记得把邻接表数据清空。
• 邻接表存图无需判断重边。

#include <iostream>
#include <algorithm>
#include <functional>
#include <queue>
#include <vector>
using namespace std;
const int
INF = 0x3f3f3f3f, MAXV = 1005, MAXE = 1005;
typedef pair<int, int> pr;

struct edge {
    int to, w;
};
int v, e, near, want;
int d[MAXV];
vector<vector<edge> > lj(MAXV);

edge Edge(int t, int w) {
    edge ret;
    ret.to = t;
    ret.w = w;
    return ret;
}
void Dijkstra(int s) {
    priority_queue<pr, vector<pr>, greater<pr> > q;
    fill(d + 1, d + v + 1, INF);
    d[s] = 0;
    q.push(pr(s, 0));

    while (!q.empty()) {
        pr tv = q.top();
        q.pop();
        int vNo = tv.first;
        if (d[vNo] < tv.second)
            continue;
        for (edge E : lj[vNo]) {
            if (d[E.to] > d[vNo] + E.w) {
                d[E.to] = d[vNo] + E.w;
                q.push(pr(E.to, d[E.to]));
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(false);

    while (cin >> e >> near >> want) {
        for (int i = 0; i < MAXV; ++i)
            lj[i].clear();
        vector<int>
            start(near + 1), end(want + 1);
        int maxV = 0;
        for (int i = 1; i <= e; ++i) {
            int f, t, c;
            cin >> f >> t >> c;
            int curMax = max(f, t);
            maxV = max(maxV, curMax);
            lj[f].push_back(Edge(t, c));
            lj[t].push_back(Edge(f, c));
        }
        v = maxV;
        for (int i = 1; i <= near; ++i) {
            cin >> start[i];
            lj[0].push_back(Edge(start[i],0)); // 把所有源点统一到0即从0向start[i]连边
        }
        for (int i = 1; i <= want; ++i) {
            cin >> end[i];
        }
        int minT = INF;
        Dijkstra(0);
        for (int i = 1; i <= want; ++i) {
            minT = min(d[end[i]], minT);
        }
        cout << minT << endl;
    }
    return 0;
}