jhrsya

用户名：1564244868

访问量：13198

签　名：

等　　级
排　　名	645
经　　验	4066
参赛次数	2
文章发表	49
年　　龄	0
在职情况	学生
学　　校	南昌大学
专　　业

　　自我简介：

TA的其他文章

数据结构-最小生成树（C++代码）
浏览：454

蓝桥杯算法提高VIP-最长公共子序列-题解(C++代码)
浏览：373

信息学奥赛一本通T1268-完全背包问题-题解(C++代码)
浏览：371

你可能喜欢

剪刀石头布（C语言代码）不知道怎么直接在scanf中用枚举变量

dijkstra算法，最小堆实现

　　作者: jhrsya　　　　发表时间：2020-02-04 10:20:55 浏览：209　|　评论：0　

使用优先级队列实现，可以把算法复杂度降至O(|E|log|V|),原题链接https://www.dotcpp.com/oj/problem1708.html

#include <queue>
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    #define INF (1 << 21) 
    
    static const int MAX = 500;
    
    	
    
    int V;
     
    struct edge{
    	int to,cost;
    	
    };
    
    typedef pair<int,int> P;
    vector<edge> G[MAX];
    int d[MAX];
    void dijkstra(int s){	//通过指定greater<P>参数， 堆按照first从小到大的顺序取出值
    	priority_queue<P, vector<P>, greater<P>> que;
    	fill(d, d + V, INF);
    	d[s] = 0;
    	que.push(P(0,s));
    	
    	while(!que.empty()){
    		P p = que.top();
    		que.pop();
    		int v = p.second;
    		if(d[v] < p.first) continue;
    		for(int i = 0; i < G[v].size(); i++){
    			edge e = G[v][i];
    			if(d[e.to] > d[v] + e.cost){
    				d[e.to] = d[v] + e.cost;
    				que.push(P(d[e.to], e.to));
    			}
    		}
    	}
    }
    int main(){
    	int s; 
    	cin >> V >> s;
    	
    	edge m;
    	for(int i = 0; i < V; i++){
    		for( m.to = 0; m.to < V; m.to++){
    			cin >> m.cost;
    			if(m.cost == 0) m.cost = INF;
    			G[i].push_back(m);
    		}
    	}
    	dijkstra(s);
    	
    	for(int i = 0; i < V; i++){
    		if(i == s) continue;
    		cout << (d[i] == INF ? -1 : d[i]) << " ";
    	}
    	
    	return 0;
    }

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

jhrsya

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-阶乘数列（C++代码）

字符串的输入输出处理（C语言代码）

C二级辅导-求偶数和（C语言代码）

剪刀石头布（C语言代码）不知道怎么直接在scanf中用枚举变量

dijkstra算法，最小堆实现

评论区

精彩推荐

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

陈教主的三角形（C语言代码）

理财计划（C语言代码）

C语言训练-大、小写问题（C语言代码）

第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略

C语言程序设计教程（第三版）课后习题10.1 （C++代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

字符串对比（C++代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

【亲和数】（C语言代码）

jhrsya

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-阶乘数列 （C++代码）

字符串的输入输出处理 （C语言代码）

C二级辅导-求偶数和 （C语言代码）

剪刀石头布 （C语言代码）不知道怎么直接在scanf中用枚举变量

dijkstra算法，最小堆实现

评论区

精彩推荐

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

陈教主的三角形 （C语言代码）

理财计划 （C语言代码）

C语言训练-大、小写问题 （C语言代码）

第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略

C语言程序设计教程（第三版）课后习题10.1 （C++代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

字符串对比 （C++代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

【亲和数】 （C语言代码）

C二级辅导-阶乘数列（C++代码）

字符串的输入输出处理（C语言代码）

C二级辅导-求偶数和（C语言代码）

剪刀石头布（C语言代码）不知道怎么直接在scanf中用枚举变量

　　评论区

陈教主的三角形（C语言代码）

理财计划（C语言代码）

C语言训练-大、小写问题（C语言代码）

字符串对比（C++代码）

【亲和数】（C语言代码）