Paul

用户名：dotcpp0596181

访问量：1263

签　名：

等　　级
排　　名	4640
经　　验	1660
参赛次数	0
文章发表	4
年　　龄	0
在职情况	学生
学　　校	华南师范大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯卡牌c++二分答案解法
浏览：801

蓝桥杯2022出差 Dijkstra简单变形
浏览：323

你可能喜欢

蓝桥杯2022出差 Dijkstra简单变形

　　作者: Paul　　　　发表时间：2023-03-24 21:45:02 浏览：323　|　评论：1　

原题链接：蓝桥杯2022年第十三届决赛真题-出差

# Dijkstra求解
## 与普通的Dijkstra不同的是：这里每个点要多一个隔离的时间
## 我们不妨将第i个点要隔离的时间记为w[i]	(w[1]=0!!!)
## 节点1到第i个点的最短距离为d[i]
## 每个节点入堆时只需要将d[i]更新为当前走过的距离+边权+在当前节点隔离的时间

```cpp
#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n' 
using namespace std;
const int INF=0x3f3f3f3f;

typedef long long ll;

inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')	f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return f*x;
}

const int N=2000;
int w[N];
int d[N];
bool vis[N];
vector<pair<int,int>> edge[N];
struct node{
	int u;
	int c;
	bool operator<(const node& y)const {return c>y.c;}	//重载运算符  距离起点更近的优先级高
};

void Dijkstra(int x){
	fore(i,0,N)	d[i]=INF;
	priority_queue<node> q;
	q.push({x,0});
	w[x]=0;
	d[x]=0;
	while(!q.empty()){
		auto p=q.top();	q.pop();
		vis[p.u]=true;
		for(auto v:edge[p.u]){
			int newd=p.c+w[p.u]+v.se;
			if(!vis[v.fi] && newd<d[v.fi]){
				q.push({v.fi,newd});
				d[v.fi]=newd;
				//cout<<v.fi<<' '<<newd<<endl;
			}
		}
	}
}

int main(){
    int n=read(),m=read();
    fore(i,1,n+1)	w[i]=read();
    while(m--){
    	int u=read(),v=read(),c=read();
    	edge[u].push_back({v,c});
    	edge[v].push_back({u,c});
    }
    Dijkstra(1);
    cout<<d[n];
	return 0; 
}

```

0.0分

4 人评分

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

　　评论区

wyh

%%%%%%%%%%%%%%

2023-03-24 22:38:25

Paul

TA的其他文章

你可能喜欢

【偶数求和】（C语言代码）记得sum的归零时机

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

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

买不到的数目（C++代码）

兰顿蚂蚁（C++代码）

蓝桥杯2022出差 Dijkstra简单变形

评论区

精彩推荐

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

WU-图形输出（C++代码）

校门外的树（C语言代码）

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

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

演讲大赛评分（C语言代码）

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

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

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

蓝桥杯基础练习VIP-报时助手（C++代码）

Paul

TA的其他文章

你可能喜欢

【偶数求和】 （C语言代码）记得sum的归零时机

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

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

买不到的数目 （C++代码）

兰顿蚂蚁 （C++代码）

蓝桥杯2022出差 Dijkstra简单变形

评论区

精彩推荐

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

WU-图形输出 （C++代码）

校门外的树 （C语言代码）

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

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

演讲大赛评分 （C语言代码）

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

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

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

蓝桥杯基础练习VIP-报时助手 （C++代码）

【偶数求和】（C语言代码）记得sum的归零时机

买不到的数目（C++代码）

兰顿蚂蚁（C++代码）

　　评论区

WU-图形输出（C++代码）

校门外的树（C语言代码）

演讲大赛评分（C语言代码）

蓝桥杯基础练习VIP-报时助手（C++代码）