山西省住房和城乡建设厅官方网站,wordpress编辑导航,企业邮箱注册申请免费注册126,东莞网站设计及拍摄方案公司话不多说先上例题。。 acwing#xff1a;178. 第K短路 给定一张 NN 个点#xff08;编号 1,2…N1,2…N#xff09;#xff0c;MM 条边的有向图#xff0c;求从起点 SS 到终点 TT 的第 KK 短路的长度#xff0c;路径允许重复经过点或边。 注意#xff1a; 每条最短路中至… 话不多说先上例题。。 acwing178. 第K短路 给定一张 NN 个点编号 1,2…N1,2…NMM 条边的有向图求从起点 SS 到终点 TT 的第 KK 短路的长度路径允许重复经过点或边。 注意 每条最短路中至少要包含一条边。 输入格式 第一行包含两个整数 NN 和 MM。 接下来 MM 行每行包含三个整数 A,BA,B 和 LL表示点 AA 与点 BB 之间存在有向边且边长为 LL。 最后一行包含三个整数 S,TS,T 和 KK分别表示起点 SS终点 TT 和第 KK 短路。 输出格式 输出占一行包含一个整数表示第 KK 短路的长度如果第 KK 短路不存在则输出 −1−1。 数据范围 1≤S,T≤N≤10001≤S,T≤N≤1000, 0≤M≤1040≤M≤104, 1≤K≤10001≤K≤1000, 1≤L≤1001≤L≤100 输入样例 2 2
1 2 5
2 1 4
1 2 2输出样例 14 思路 整体思路就是先逆向求一次dijkstral将各点到目标点的最短路求出来以此作为A*的估计值。然后在采用A*求第K短路当第K次目标点出队列是返回值即可。注意起点终点一直时需要将k1将原地不动的情况除去。 上代码 #includebits/stdc.h
using namespace std;
typedef pairint,int PII;
typedef pairint,PII PIII;
#define y second
#define x first
const int N1010,M3e410;
int s, t ,k;
int n,m;
int h[N],h2[N],e[M],ne[M],w[M],idx;
int dis[N],cnt[N];
bool st[N];
void add(int h[],int a,int b,int c){e[idx]b,w[idx]c,ne[idx]h[a],h[a]idx;
}
void dijkstral(){memset(dis,0x3f,sizeof(dis));priority_queuePII,vectorPII,greaterPIIq;dis[t]0;q.push({0,t});while(q.size()){auto Tq.top();q.pop();int uT.y;if(st[u]){continue;}st[u]true;for(int ih2[u];~i;ine[i]){int je[i];if(st[j]){continue;}if(dis[j]dis[u]w[i]){dis[j]dis[u]w[i];q.push({dis[j],j});}}}
}
int astar(){priority_queuePIII,vectorPIII,greaterPIII q;q.push({dis[s],{0,s}});while(q.size()){auto Tq.top();q.pop();int distT.y.x;int uT.y.y;cnt[u];if(cnt[t]k){return dist;}for(int ih[u];~i;ine[i]){int je[i];if(cnt[j]k){continue;}q.push({distw[i]dis[j],{distw[i],j}});}}return -1;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);memset(h,-1,sizeof(h));memset(h2,-1,sizeof(h2));cinnm;for(int i1;im;i){int a,b,c;cinabc;add(h,a,b,c);add(h2,b,a,c);}cinstk;dijkstral();if(st){k;}int ansastar();coutans;
} 这里附上一道例题求次短路。。 算是A*的特殊情况了去直接秒杀吧。 acwing133. 第二短路 贝茜把家搬到了一个小农场但她常常回到 FJ 的农场去拜访她的朋友。 贝茜很喜欢路边的风景不想那么快地结束她的旅途于是她每次回农场都会选择第二短的路径而不像我们所习惯的那样选择最短路。 贝茜所在的乡村有 RR 条双向道路每条路都连接了所有的 NN 个农场中的某两个。 贝茜居住在农场 11她的朋友们居住在农场 NN即贝茜每次旅行的目的地。 贝茜选择的第二短的路径中可以包含任何一条在最短路中出现的道路并且一条路可以重复走多次。 当然第二短路的长度必须严格大于最短路可能有多条的长度但它的长度必须不大于所有除最短路外的路径的长度。 输入格式 第一行包含两个整数 NN 和 RR。 接下来 RR 行每行包含三个整数 A,B,DA,B,D表示农场 AA 和农场 BB 之间存在一条长度为 DD 的路。 输出格式 输出仅包含一个整数表示从农场 11 到农场 NN 的第二短路的长度。 数据范围 1≤R≤1051≤R≤105, 1≤N≤50001≤N≤5000, 1≤D≤50001≤D≤5000, 1≤A,B≤N1≤A,B≤N 输入样例 4 4
1 2 100
2 4 200
2 3 250
3 4 100输出样例 450 #includebits/stdc.h
using namespace std;
const int N5010,M4e510;
#define x first
#define y second
typedef pairint,intPII;
typedef pairint,PIIPIII;
int h[N],e[M],ne[M],w[M],idx;
int dis[N];
bool st[N];
int cnt[N];
int n,m;void add(int a,int b,int c){e[idx]b,w[idx]c,ne[idx]h[a],h[a]idx;
}
void dijkstral()
{memset(dis,0x3f,sizeof(dis));priority_queuePII,vectorPII,greaterPIIq;q.push({0,n});dis[n]0;while(q.size()){auto tq.top();q.pop();int vt.y;if(st[v]){continue;}st[v]true;for(int ih[v];~i;ine[i]){int je[i];if(st[j]){continue;}if(dis[j]dis[v]w[i]){dis[j]dis[v]w[i];q.push({dis[j],j});}}}
}
int astar(){int flag0;priority_queuePIII,vectorPIII,greaterPIIIq;q.push({dis[1],{0,1}});while(q.size()){auto tq.top();q.pop();int vt.y.y;int distt.y.x;cnt[v];if(cnt[n]1){flagdist;}if(cnt[n]2distflag){return dist;}for(int ih[v];~i;ine[i]){int je[i];if(cnt[j]2){continue;}q.push({distdis[j]w[i],{distw[i],j}});}}
}
int main()
{ios::sync_with_stdio(0);cout.tie(0),cin.tie(0);memset(h,-1,sizeof(h));cinnm;for(int i1;im;i){int a,b,c;cinabc;add(a,b,c);add(b,a,c);}dijkstral();int ansastar();coutans;
}
