【最短路-spfa算法+dfs】L2-001. 紧急救援

小鱼儿 2022-05-29 04:38 184阅读 0赞

Think:  
1.题意：n个城市，每个城市含有ai支救援队，现在需要以最短的路径从城市 s 到达城市 e，沿途经过的城市的救援队共同赶往。  
现在询问：  
（1）.最短路径的条数  
（2）.最短路径中所能汇聚的最多救援队  
（3）.汇聚最多救援队的最短路径经过的城市  
2.知识点：【最短路-spfa算法+dfs】  
3.思路：  
（1）.通过spfa算法求解最短路径中所能汇聚的最多救援队（二重限制）、汇聚最多救援队的最短路径经过的城市（记录路径）  
（2）.通过dfs求解最短路径的条数（剪枝优化）  
4.代码：

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 504;
    
    struct Edge{
        int v, w;
        int next;
    }edge[N*N];
    
    int cnt, head[N];
    int n, m, s, e, gra[N][N];
    int tac, rec[N], sum[N], vis[N], dis[N], pre[N];
    queue<int> q;
    
    void add_edge(int u, int v, int w);
    void dfs(int u);
    void spfa();
    void get_path(int u);
    
    int main(){
        int i, j, u, v, w;
        scanf("%d %d %d %d", &n, &m, &s, &e);
        for(i = 0; i < n; i++)
            scanf("%d", &rec[i]);
        memset(gra, inf, sizeof(gra));
        for(i = 0; i < m; i++){
            scanf("%d %d %d", &u, &v, &w);
            if(w < gra[u][v])
                gra[u][v] = gra[v][u] = w;
        }
        cnt = 0;
        memset(head, -1, sizeof(head));
        for(i = 0; i < n; i++){
            for(j = i+1; j < n; j++){
                if(gra[i][j] != inf){
                    add_edge(i, j, gra[i][j]);
                    add_edge(j, i, gra[i][j]);
                }
            }
        }
    
        spfa();
    
        tac = 0;
        memset(vis, 0, sizeof(vis));
        vis[s] = 1;
        dfs(s);
    
        printf("%d %d\n", tac, sum[e]);
        get_path(e);
        printf("\n");
        return 0;
    }
    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++;
        return;
    }
    void dfs(int u){
        if(u == e){
            tac++;
            return;
        }
        for(int i = head[u]; ~i; i = edge[i].next){
            int v = edge[i].v;
            int w = edge[i].w;
            if(!vis[v] && dis[v] == dis[u] + w){
                vis[v] = 1;
                dfs(v);
                vis[v] = 0;
            }
        }
        return;
    }
    void spfa(){
        int i, u, v, w;
        while(!q.empty()){
            q.pop();
        }
        memset(vis, 0, sizeof(vis));
        memset(dis, inf, sizeof(dis));
        memset(sum, 0, sizeof(sum));
        memset(pre, -1, sizeof(pre));
        vis[s] = 1, dis[s] = 0, sum[s] = rec[s];
    
        q.push(s);
        while(!q.empty()){
            u = q.front();
            q.pop();
            vis[u] = 0;/*出队标记*/
            for(i = head[u]; ~i; i = edge[i].next){
                v = edge[i].v;
                w = edge[i].w;
                if(dis[v] > dis[u] + w){
                    dis[v] = dis[u] + w;
                    sum[v] = sum[u] + rec[v];
                    pre[v] = u;
                    if(!vis[v]){
                        vis[v] = 1;
                        q.push(v);
                    }
                }
                else if(dis[v] == dis[u] + w){
                    if(sum[v] < sum[u] + rec[v]){
                        sum[v] = sum[u] + rec[v];
                        pre[v] = u;
                    }
                    if(!vis[v]){
                        vis[v] = 1;
                        q.push(v);
                    }
                }
            }
        }
        return;
    }
    void get_path(int u){
        if(pre[u] != -1) get_path(pre[u]);
        if(pre[u] == -1) printf("%d", u);
        else printf(" %d", u);
        return;
    }