AcWing 1137. 选择最佳线路

一、超级源点法

最短路多个起点，不需要做多遍最短路，只需要构造一个超级源点，使其到其他起点的花费都是\(0\)，以这点为起点做一遍最短路即可，图论中一种很常见的小技巧。如果加边了，注意\(N\)和\(M\)的范围要多开一些。
这个思路可以扩展到求解从多个起点到多个终点的模型上面

1、SPFA

#include 
using namespace std;
typedef pair PII;
//建立虚拟源点0
const int N = 1010, M = 40010;
const int INF = 0x3f3f3f3f;
int n, m, s;

//邻接表
int h[N], e[M], w[M], ne[M], idx;
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int d[N];   //最短距离数组
bool st[N]; //是不是进过队列

// spfa模板
void spfa(int start) {
    queue q;
    //将所有距离初始化为无穷大
    memset(d, 0x3f, sizeof d);
    //出发点的距离清零
    d[start] = 0;

    q.push(start);    //出发点入队列
    st[start] = true; //出发点标识已使用

    while (q.size()) {
        int t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[j] > d[t] + w[i]) {
                d[j] = d[t] + w[i];
                if (!st[j]) {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
}
int main() {
    //多组测试数据，建议用scanf来读
    while (~scanf("%d%d%d", &n, &m, &s)) {
        //注意清空链表头
        memset(h, -1, sizeof h);
        idx = 0;
        // m条边
        while (m--) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
        }
        int x;
        scanf("%d", &x);
        while (x--) {
            int start;
            scanf("%d", &start);
            add(0, start, 0);
        }
        spfa(0);
        if (d[s] == INF)
            cout << -1 << endl;
        else
            cout << d[s] << endl;
    }
    return 0;
}

2、Dijkstra

#include 
using namespace std;
typedef pair PII;
//建立虚拟源点0
const int N = 1010, M = 40010;
const int INF = 0x3f3f3f3f;
int n, m, s;

//邻接表
int h[N], e[M], w[M], ne[M], idx;
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int d[N];   //最短距离数组
bool st[N]; //是否进过队列
//迪杰斯特拉
int dijkstra(int start) {
    memset(d, 0x3f, sizeof d);                        //初始化大
    memset(st, 0, sizeof st);                         //初始化为未出队列过
    priority_queue, greater> q; //小顶堆
    q.push({start, 0});                               //出发点入队列
    d[start] = 0;                                     //出发点距离0
    while (q.size()) {
        auto t = q.top();
        q.pop();
        int u = t.second;
        if (st[u]) continue;
        st[u] = true;
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[j] > d[u] + w[i]) {
                d[j] = d[u] + w[i];
                q.push({d[j], j});
            }
        }
    }
    return d[s] == INF ? -1 : d[s];
}
int main() {
    //多组测试数据，建议用scanf来读
    while (~scanf("%d%d%d", &n, &m, &s)) {
        //注意清空链表头
        memset(h, -1, sizeof h);
        idx = 0;
        // m条边
        while (m--) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
        }
        int x;
        scanf("%d", &x);
        while (x--) {
            int start;
            scanf("%d", &start);
            add(0, start, 0);
        }
        cout << dijkstra(0) << endl;
    }
    return 0;
}

二、反向建图法

1、SPFA

#include 
using namespace std;
typedef pair PII;
const int INF = 0x3f3f3f3f;
const int M = 2e5 + 5, N = 1005;
//存图
int idx, h[N], e[M], w[M], ne[M];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int n, m;   // n个点，m条边
int S;      //出发点
int d[N];   //距离数组
bool st[N]; // Dijkstra是不是入过队列

void spfa(int start) {
    //多轮使用spfa，所以一定要清空
    memset(st, 0, sizeof st);
    memset(d, 0x3f, sizeof d);
    d[start] = 0;

    //普通队列
    queue q;
    q.push(start);
    st[start] = true; // st数组标记当前在队列中的点

    while (q.size()) {
        int u = q.front();
        q.pop();
        st[u] = false; //出队列，u不在队列中了

        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[u] + w[i] < d[j]) {
                d[j] = d[u] + w[i];
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
}
int main() {
    while (cin >> n >> m >> S) {
        //初始化
        memset(st, 0, sizeof st);
        memset(h, -1, sizeof h);
        idx = 0;
        int ans = INF;

        while (m--) {
            int a, b, c;
            cin >> a >> b >> c;
            add(b, a, c); //反向建边
        }
        //最短路
        spfa(S);
        int T; // T个终点
        int x; //终点ID
        cin >> T;
        while (T--) {
            cin >> x;
            ans = min(ans, d[x]);
        }
        printf("%d\n", ans == INF ? -1 : ans);
    }
    return 0;
}

2、Dijkstra法

#include 
using namespace std;
typedef pair PII;
const int INF = 0x3f3f3f3f;
const int M = 2e5 + 5, N = 1005;
//存图
int idx, h[N], e[M], w[M], ne[M];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int n, m;   // n个点，m条边
int S;      //出发点
int d[N];   //距离数组
bool st[N]; // Dijkstra是不是入过队列

void dijkstra() {
    priority_queue, greater> q;
    q.push({0, S});
    d[S] = 0;
    while (q.size()) {
        auto t = q.top();
        int u = t.second, dist = t.first;
        q.pop();
        if (st[u]) continue;
        st[u] = true;
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[j] > dist + w[i]) {
                d[j] = dist + w[i];
                q.push({d[j], j});
            }
        }
    }
}
int main() {
    while (cin >> n >> m >> S) {
        //初始化
        memset(st, 0, sizeof st);
        memset(h, -1, sizeof h);
        memset(d, 0x3f, sizeof d);
        idx = 0;
        int ans = INF;

        while (m--) {
            int a, b, c;
            cin >> a >> b >> c;
            add(b, a, c); //反向建边
        }
        //最短路
        dijkstra();
        int T; // T个终点
        int x; //终点ID
        cin >> T;
        while (T--) {
            cin >> x;
            ans = min(ans, d[x]);
        }
        printf("%d\n", ans == INF ? -1 : ans);
    }
    return 0;
}