题目传送门
一些废话
今天登洛谷的时候发现主页少了一道紫题。
？？？怎么降绿了 （建议升蓝） ？？？
AND这是蒟蒻的第一篇题解
简介
- 很容易地想到，这是一道最短路问题，要求在一个有 \(N\) 个站点和 \(M\) 条地铁线路的图中，从站点 \(1\) 到站点 \(N\) 的最小花费。
- 每条线路由一个公司运营，乘坐同一公司的线路花费 \(1\) 元，换乘到其他公司的线路需要再花费 \(1\) 元。
思路
算法选择
这里使用 SPFA算法 来解决这个问题。SPFA 算法可以很好地处理带权图中的最短路问题，并且可以处理存在负权边的情况（虽然本题中没有负权边）。
细节处理
建图
本人特别喜欢用 链式前向星
因为它可以存各种图
void ADD(int x,int y,int z) {
ver[++tot]=y;
edge[tot]=z;
Next[tot]=head[x];
head[x]=tot;
}
//main
memset(head,-1,sizeof(head));
tot=-1;
for(int i = 1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
ADD(x,y,z);
ADD(y,x,z);
}
算法实现
-
定义一个set，用于存储每个节点已经访问过的公司编号，这样可以避免重复计算同一种公司换乘的情况。
-
定义Find函数，其中x是当前节点，y是要判断的边所属的公司编号。通过检查 \(num[x]\) 集合中是否包含 \(y\) 来确定是否需要换乘
bool Find(int x,int y) {
if(num[x].count(y)){
return 0;
}
else{
return 1;
}
}
- 跑一遍SPFA
最终结果输出
检查 \(dist[n]\) 的值。如果无法到达站点，输出-1；否则输出 \(dist[n]\) ，即从站点 1 到站点的最小花费。