N - Tram——最短路_spfa()算法

骑猪看日落 2022-06-12 10:26 183阅读 0赞

Think:  
1知识点：最短路\_spfa()算法  
2思考：理解题意进而建图

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 1e2 + 4;
    
    int n, e[N][N], vis[N], dis[N];
    
    void spfa(int x);
    
    int main(){
        int x, y, k, i, j, v;
        while(~scanf("%d %d %d", &n, &x, &y)){
            memset(e, inf, sizeof(e));
            for(i = 1; i <= n; i++){
                scanf("%d", &k);
                for(j = 0; j < k; j++){
                    scanf("%d", &v);
                    if(!j)
                        e[i][v] = 0;
                    else
                        e[i][v] = 1;
                }
            }
            spfa(x);
            if(dis[y] != inf)
                printf("%d\n", dis[y]);
            else
                printf("-1\n");
        }
        return 0;
    }
    void spfa(int x){
        queue <int> q;
        while(!q.empty()){
            q.pop();
        }
        memset(dis, inf, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        dis[x] = 0, vis[x] = 1;
        q.push(x);
        while(!q.empty()){
            int t1 = q.front();
            q.pop();
            vis[t1] = 0;
            for(int i = 1; i <= n; i++){
                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/N

发表评论取消回复

表情：

评论列表（有 0 条评论，183人围观）

还没有评论，来说两句吧...

相关阅读

相关最短路（Spfa）

问题描述给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。输入格式第一行两个整数n,

迈不过友情╰/ 2022年09月27日 06:49/ 0 赞/ 168 阅读

相关 nyoj1006（最短路次短路spfa）

偷西瓜时间限制： 1000 ms | 内存限制： 65535 KB 难度： 4 描述对于农村的孩子来说最大的乐趣，莫过于和小伙伴们一块下地偷西瓜了，虽然孩子们条

布满荆棘的人生/ 2022年08月27日 04:56/ 0 赞/ 189 阅读

相关 N - Tram——最短路_spfa()算法

Think: 1知识点：最短路\_spfa()算法 2思考：理解题意进而建图 [vjudge题目链接][vjudge] 以下为Accepted代码 inc

骑猪看日落/ 2022年06月12日 10:26/ 0 赞/ 184 阅读

相关 K - Candies——最短路_spfa()算法

Think: 1知识点： 1>最短路\_spfa()算法+前向星 2>差分约束系统：[差分约束系统——百度百科][Link 1] 2思考：队列超时，栈通过——w

浅浅的花香味﹌/ 2022年06月12日 09:29/ 0 赞/ 193 阅读

相关 J - Invitation Cards——最短路_spfa()算法

Think: 1知识点：最短路\_spfa()算法+前向星 2反思： 1>函数中形参和实参的传递，数组传进的为地址，形参改变实参相应的改变，而传进的标记变量形参改变

超、凢脫俗/ 2022年06月12日 09:16/ 0 赞/ 178 阅读

相关 I - Arbitrage ——最短路_spfa()算法

Think: 1知识点：最短路\_spfa()算法——判断环的存在 2反思： 1>要努力做到善于总结，勤于反思 2>吸收空格 [vjudge题目链接][vju

一时失言乱红尘/ 2022年06月12日 09:10/ 0 赞/ 185 阅读

相关 G - MPI Maelstrom——最短路_spfa()算法

Think: 1知识点：最短路\_spfa()算法 2反思：memset()初始化函数注意第三个参数不要传错 [建议参考题意分析][Link 1] [vjudge题

我不是女神ヾ/ 2022年06月12日 06:13/ 0 赞/ 203 阅读

相关 E - Currency Exchange——最短路_spfa()算法

Think: 1知识点：最短路\_spfa()算法+前向星 2反思：判断环是否存在 [建议参考题意分析][Link 1] [vjudge题目链接][vjudge]

向右看齐/ 2022年06月12日 05:58/ 0 赞/ 179 阅读

相关 D - Silver Cow Party——最短路_spfa()算法

Think: 1知识点：最短路\_spfa()算法 2反思：图的初始化 3思路：通过正向边spfa()求出回去的，反向边spfa()求出到达的 [建议参考题意分析

怼烎@/ 2022年06月12日 05:54/ 0 赞/ 171 阅读

相关【最短路-spfa算法】Road Construction Aizu - 2249

Think: 1知识点：最短路-spfa算法 2题意：n个城市m条路，每条路的信息包括起点(u)、终点(v)、长度(d)、花费(c)，询问在保证1号城市到其它城市距离最

比眉伴天荒/ 2022年05月31日 01:42/ 0 赞/ 169 阅读