题解 | #单源最短路-Dijkstra算法#

单源最短路

https://www.nowcoder.com/practice/9f15b34a2a944a7798a5340ff0dba8b7

    int findShortestPath(int nint mvector<vector<int> >& graph) {

        vector<vector<int> >G(n,vector<int>(n,INT32_MAX));
        
//重边害死菜鸡本尊,两个顶点有多条有向边时,用短边
        for(int i=0;i<m;i++)
            G[(graph[i][0]-1)][(graph[i][1]-1)]=min(graph[i][2],G[(graph[i][0]-1)][(graph[i][1]-1)]);

        for(int i=0;i<n;i++) G[i][i]=0;

        vector<intdist(n,INT32_MAX);

        for(int i=0;i<n;i++) dist[i] = G[0][i];

        for(int i=1;i<n;i++) 
            for(int j=1;j<n;j++)
                if(dist[i]!=INT32_MAX&&G[i][j]!=INT32_MAX)
                    dist[j] = min(dist[j],dist[i]+G[i][j]);

        //for(int i:dist) cout<<"dist[i]:"<<i<<endl;

        return dist[n-1]==INT32_MAX?-1:dist[n-1];
        // write code here
    }
全部评论

相关推荐

合不合适,我自己说了才算
码农索隆:hr:“真执着啊,来我公司当法人吧”
点赞 评论 收藏
分享
每晚夜里独自颤抖:你cet6就cet6,cet4就cet4,你写个cet证书等是什么意思。专业技能快赶上项目行数,你做的这2个项目哪里能提现你有这么多技能呢
点赞 评论 收藏
分享
码农索隆:有点耳熟,你们是我教过最差的一届
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务