1 Star 0 Fork 1

saigon/Algorithms

forked from charlieshu/Algorithms 
加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
克隆/下载
P1346_电车.cpp 3.46 KB
一键复制 编辑 原始数据 按行查看 历史
charlie 提交于 2024-01-09 00:01 . move from github to gitee
#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
*/
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
C++
1
https://gitee.com/saigonshu/algorithm.git
git@gitee.com:saigonshu/algorithm.git
saigonshu
algorithm
Algorithms
master

搜索帮助

0d507c66 1850385 C8b1a773 1850385