[蓝桥杯练习题]出差

一道DJ题,重要的是隔离时间,把隔离时间加在边权上即可
现实生活的题大多都是无向图建图,需要边的两端点各自上邻接表和相同权重

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1005;
const int M=10005;
struct edge{
	int to;
	ll w;
	edge(int a,int b){to=a;w=b;}
};
struct node{//dj有个node结构体,里面的setdis和外部定义的setdis很重要 
	int id;ll sdis;
	node(int num,ll len){id=num;sdis=len;}
	bool operator <(const node& cur)const{return sdis > cur.sdis;}
};
int geli[N];
vector<vector<edge>>adjtable(M);
priority_queue<node>wait;
ll sdis[N];
bool hasmin[M];
bool haspath[N];

void dj(){
	while(!wait.empty()){
		node cur = wait.top();wait.pop();//取出离起点最近的点为当前点
		if(hasmin[cur.id])continue;//若起点有到当前点的最短路径了就跳过
		hasmin[cur.id]=true;haspath[cur.id]=true;
		for(edge adj:adjtable[cur.id]){//对某个结点的邻接表遍历 
			if(hasmin[adj.to])continue;//若起点有到该邻点的最短路径了就跳过 
			if(sdis[adj.to] > adj.w + cur.sdis){//若起点到邻点的最短距离 大于 当前点到邻点的距离 与 起点到当前点的最短距离 之和 
				sdis[adj.to] = adj.w + cur.sdis;//则更新 起点到邻点 的最短距离为  起点中转当前点再到邻点 的距离 
				wait.push(node(adj.to,sdis[adj.to]));//将邻点放入小根堆,与堆内其余邻点比较起点距,小者排前,下一轮优先弹出 
}	}	}	}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	memset(sdis,0x7f,sizeof(sdis));
	int n,m;cin>>n>>m;
	for(int i=1;i<=n;++i)cin>>geli[i];
	int start=1,end=n;geli[end]=0;
	int a,b,c;
	for(int i=1;i<=m;++i){
		cin>>a>>b>>c;
		adjtable[a].push_back(edge(b,c+geli[b]));//无向图,两边都可以互相走,不可只声明一条有向边,而是不同点的互相有向边
		adjtable[b].push_back(edge(a,c+geli[a]));
	}
	// for(int i=1;i<n;++i){
	// 	for(edge& adj:adjtable[i])
	// 		adj.w+=geli[i];
	// }
//	for(int i=1;i<=n;++i)for(edge& adj:adjtable[i])cout<<i<<" "<<adj.to<<" "<<adj.w<<endl;
	wait.push(node(start,0));
	dj();
	if(hasmin[end]&&haspath[end])cout<<sdis[end];
	return 0;
} 
/*
4 4
5 7 3 4
1 2 4
1 3 5
2 4 3
3 4 5
*/