jhrsya

用户名：1564244868

访问量：13193

签　名：

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

　　自我简介：

TA的其他文章

数据结构-堆排序-题解(C语言代码)
浏览：892

数据结构-图的遍历——DFS深度优先搜索-题解(C语言代码)
浏览：781

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

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

dijkstra算法变形，次短路问题

　　作者: jhrsya　　　　发表时间：2020-02-04 11:54:45 浏览：147　|　评论：0　

![题目](/image_editor_upload/20200204115752_44848.jpg "题目")

#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 dist[MAX];		//最短路 
    int dist2[MAX];		//次短路 
    void dijkstra(){
    	priority_queue<P, vector<P>, greater<P>> que;
    	fill(dist, dist + V, INF);
    	fill(dist2, dist2 + V, INF);
    	dist[0] = 0;
    	que.push(P(0,0));
    	
    	while(!que.empty()){
    		P p = que.top();
    		que.pop();
    		int v = p.second, d = p.first;
    		if(dist2[v] < p.first) continue;
    		for(int i = 0; i < G[v].size(); i++){
    			edge e = G[v][i];
    			int d2 = d + e.cost;
    			if(dist[e.to] > d2){		//最短路更新 
    				swap(dist[e.to], d2);
    				que.push(P(dist[e.to], e.to));
    			}
    			if(dist2[e.to] > d2 && dist[e.to] < d2){		//次短路更新 
    				dist2[e.to] = d2;
    				que.push(P(dist2[e.to],e.to));
    			}
    		}
    	}
    	cout << dist2[V - 1] << endl;
    }
    int main(){
    	
    	cin >> V ;
    	
    	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();
    	
    	
    	return 0;
    }

0.0分

2 人评分

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

jhrsya

TA的其他文章

你可能喜欢

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

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

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

你的开发任务（C++代码）写到一半，等有心情回来补全

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

dijkstra算法变形，次短路问题

评论区

精彩推荐

点我有惊喜！你懂得！

C语言训练-舍罕王的失算（C++代码）（都给答案了还算什么）

K-进制数（C++代码）

A+B for Input-Output Practice (VII) （C++代码）

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

计算质因子（C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

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

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

jhrsya

TA的其他文章

你可能喜欢

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

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

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

你的开发任务 （C++代码）写到一半，等有心情回来补全

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

dijkstra算法变形，次短路问题

评论区

精彩推荐

点我有惊喜！你懂得！

C语言训练-舍罕王的失算 （C++代码）（都给答案了还算什么）

K-进制数 （C++代码）

A+B for Input-Output Practice (VII) （C++代码）

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

计算质因子 （C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

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

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

你的开发任务（C++代码）写到一半，等有心情回来补全

　　评论区

C语言训练-舍罕王的失算（C++代码）（都给答案了还算什么）

K-进制数（C++代码）

计算质因子（C++代码）