I - 浪里个浪 FZU - 2261——最短路_spfa算法(多起点-多终点)

布满荆棘的人生 2022-06-11 00:06 141阅读 0赞

Think:  
1知识点：最短路\_spfa算法(多起点-多终点)  
2思考：将起点vis置为1,dis置为0,spfa算法,然后dis数组取多终点中的最小值  
3优化思路：创建源点0和汇点n+1，将源点0与所有起点连边(无向边),边权为0，将所有终点与汇点n+1连边(无向边),边权为0；然后spfa算法求0点到n+1点的最短路即可

[vjudge题目链接][vjudge]

以下为Accepted代码——多起点\_多终点

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 1e5 + 4e2;
    const int M = 1e5 + 4e2;
    
    struct Edge{
        int v;
        int w;
        int next;
    }edge[M];
    
    int cnt, head[N], vis[N], dis[N], a[N], b[N];
    int op, tp, link[N];
    
    void Init(int n);
    void add_edge(int u, int v, int w);
    void spfa();
    
    int main(){
        int n, m, i, u, v, w, len_a, len_b;
        while(~scanf("%d %d", &n, &m)){
            cnt = 0;
            Init(n);
            while(m--){
                scanf("%d %d %d", &u, &v, &w);
                add_edge(u, v, w);
            }
            memset(vis, 0, sizeof(vis));
            memset(dis, inf, sizeof(dis));
            scanf("%d", &len_a);
            op = tp = 0;
            for(i = 0; i < len_a; i++){
                scanf("%d", &a[i]);
                vis[a[i]] = 1;
                dis[a[i]] = 0;
                link[tp++] = a[i];
            }
            scanf("%d", &len_b);
            for(i = 0; i < len_b; i++){
                scanf("%d", &b[i]);
            }
            spfa();
            int miv = inf;
            for(i = 0; i < len_b; i++){
                miv = min(miv, dis[b[i]]);
            }
            printf("%d\n", miv);
        }
        return 0;
    }
    void Init(int n){
        for(int i = 1; i <= n; i++)
            head[i] = -1;
    }
    void add_edge(int u, int v, int w){
        edge[cnt].v = v;
        edge[cnt].w = w;
        edge[cnt].next = head[u];
        head[u] = cnt++;
    }
    void spfa(){
        while(op < tp){
            int u = link[op];
            vis[u] = 0;
            for(int i = head[u]; ~i; i = edge[i].next){
                int v = edge[i].v;
                int w = edge[i].w;
                if(dis[u] + w < dis[v]){
                    dis[v] = dis[u] + w;
                    if(!vis[v]){
                        vis[v] = 1;
                        link[tp++] = v;
                    }
                }
            }
            op++;
        }
    }

[vjudge]: https://vjudge.net/contest/173353#problem/I