代码拉取完成,页面将自动刷新
同步操作将从 charlieshu/Algorithms 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
#include <iostream>
#include <queue>
using namespace std;
struct node{
int id; //节点id
int cw; // start点到该点的最小距离
bool operator < ( const node & y ) const{ // 反向 < 操作符, 以逆转priority_queue的默认排序
return y.cw < cw;
}
};
struct edge{
int v; // 终点ID , 起点是记录第一条edge的edgesHead的序号
int w; // 该边权值
int next; // 同一起点的下一条边,如果没有下一条,该值为 -1 , 目的是为了加快处理某个起点的所有边
};
priority_queue<node> pqq; // 去向 回向复用
int kMax=0x6fffffff;
void dijstra(int start, int stop, int* dists, bool* used, int n, edge* edges, int* edgeHeads, int m){
dists[start] = 0;
pqq.push((node){start, 0});
while(!pqq.empty()){
node minNode = pqq.top();
pqq.pop();
// cout<<"process: {id="<<minNode.id<<", cw="<<minNode.cw<<"}"<<endl;
// 检查minNode是否已经得到最小dist
if(minNode.id==stop) return;
if(used[minNode.id]) continue;
used[minNode.id] = 1;
// 使用 minNode的所有edge来更新dists
int u = minNode.id;
int edgeIndex = edgeHeads[u];
while(edgeIndex>=0){ // 最后一条边的next为-1
edge e = edges[edgeIndex];
// cout<<" handle edge: {v="<<e.v<<" w="<<e.w<<" next="<<e.next<<"}"<<endl;
if(dists[u]+e.w<dists[e.v]){ // 借由 minNode到e.v点的距离更短,要更新并且将e.v点加入到queue中,等下一次处理之
// cout<<" select edge: {v="<<e.v<<" w="<<e.w<<" next="<<e.next<<"}"<<endl;
dists[e.v] = dists[u]+e.w;
pqq.push((node){e.v, dists[e.v]});
}
edgeIndex = e.next;
}
}
}
int main(){
// 1. init data from input
int n,start,stop;
cin>>n>>start>>stop;
start--;stop--;
int m = n*n;
/* edges与 edgeHeads 的配合来快速找到一个节点的所有边, 比如:
edges[1].v=3 ... edges[3].v=12 ... edges[99].v=102 ....
.next=3 ... .next=99 ... .next=-1 ....
edgeHeads[10] = 1
上面数据表示: 节点10 有3条edge分别到节点 3、12、102
*/
edge edges[m]; // {v,w}
int edgeHeads[n]; // edgeHeads[u] == last {v,w} of node u
int dists[n]; // node start 到 该node的最小值
bool used[n]={0}; // 已经得到最小值的标志, 1 为已经得到
for(int i=0;i<n;i++){
dists[i]=kMax; // 由于是记录最小值, 所以初始化为最大值
edgeHeads[i]=-1; // -1 为edge.next的完结标志位
}
int realM=0, mIndx = 0;
int k,u,v,w;
for(int i=0;i<n;i++){
cin>>k;
realM += k;
u = i;
for(int j=0; j<k; j++){
cin>>v;
v--;
w = (j==0)?0:1;
edges[mIndx]=(edge){v, w, edgeHeads[u]}; // edgeHeads[u]现在为node u的上一条边序号
// cout<<"edge: "<<"v="<<v<<" w="<<w<<" next="<<edgeHeads[u]<<endl;
edgeHeads[u] = mIndx; // 记住 node v的最后一条边的序号
mIndx++;
}
}
// 2. dijstra 使用dijstra算法算正向单源点start
// cout<<"n="<<n<<" realM="<<realM<<endl;
dijstra(start, stop, dists, used, n, edges, edgeHeads, realM);
// 3. output
int sum = 0;
cout<<((dists[stop]==kMax)?-1:dists[stop]);
return 0;
}
/*
test1, expect 0
================
3 2 1
2 2 3
2 3 1
2 1 2
test2, expect 1
================
4 2 3
3 4 2 3
2 4 3
2 1 4
2 2 3
test3, expect 0
================
4 1 4
3 4 2 3
2 4 3
2 1 4
2 2 3
test4, expect 0
================
4 1 4
3 4 2 3
2 4 3
3 1 4 3
4 2 3 4 4
test5, expect 1
================
4 3 4
4 1 4 2 3
2 4 3
3 1 4 3
4 2 3 4 4
test6, expect 1
================
4 3 2
1 3
2 1 3
2 1 2
2 1 3
test7, expect -1
================
4 3 2
1 3
2 1 3
2 1 4
2 1 3
*/
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。