M - 昂贵的聘礼——最短路_spfa()算法

心已赠人 2022-06-12 10:11 125阅读 0赞

Think:  
1知识点：最短路\_spfa()算法+区间移动  
2思考：通过知识扩展思路，敢于尝试，善于借鉴，一定要有自己的思想与创新点

[vjudge题目链接][vjudge]

[建议参考博客][Link 1]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 1e2 + 4;
    
    int n, m, e[N][N], dis[N], vis[N], lev[N];
    
    void spfa(int l, int r);
    
    int main(){
        int i, j, p, k, u, w, ans;
        while(~scanf("%d %d", &m, &n)){
            ans = inf;
            memset(e, inf, sizeof(e));
            for(i = 1; i <= n; i++){
                scanf("%d %d %d", &p, &lev[i], &k);
                e[0][i] = p;/*模拟入队预处理，使得初始状态全部入队，进而更新*/
                for(j = 1; j <= k; j++){
                    scanf("%d %d", &u, &w);
                    e[u][i] = w;
                }
            }
            for(i = 0; i <= m; i++){
       /*区间移动寻找最优解*/
                spfa(lev[1]-i, lev[1]+m-i);
                ans = min(ans, dis[1]);
            }
            printf("%d\n", ans);
        }
        return 0;
    }
    void spfa(int l, int r){
        queue <int> q;
        while(!q.empty()){
            q.pop();
        }
        memset(dis, inf, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        dis[0] = 0, vis[0] = 1;
        q.push(0);
        while(!q.empty()){
            int t1 = q.front();
            q.pop();
            vis[t1] = 0;
            for(int i = 1; i <= n; i++){
                if(lev[i] < l || lev[i] > r)
                    continue;
                if(dis[t1] + e[t1][i] < dis[i]){
                    dis[i] = dis[t1] + e[t1][i];
                    if(!vis[i]){
                        vis[i] = 1;
                        q.push(i);
                    }
                }
            }
        }
    }

[vjudge]: https://vjudge.net/contest/163006#problem/M
[Link 1]: http://blog.csdn.net/u011265346/article/details/42557961