82 lines
2.6 KiB
C++
82 lines
2.6 KiB
C++
|
#include <bits/stdc++.h>
|
|||
|
|
|
|||
|
|
using namespace std;
|
|||
|
|
const int INF = 0x3f3f3f3f;
|
|||
|
|
typedef pair<int, int> PII;
|
|||
|
|
|
|||
|
|
<<<<<<< HEAD
|
|||
|
|
const int N = 1e5 + 10;
|
|||
|
|
const int M = N * 2;
|
|||
|
|
=======
|
|||
|
|
const int N = 1e5 + 10, M = N << 1;
|
|||
|
|
>>>>>>> 273b1ba54225ce58787e704d3a022dc4b01a35b0
|
|||
|
|
|
|||
|
|
int n; // 总共有N个车站
|
|||
|
|
int m; // 开通了M条单程巴士线路
|
|||
|
|
int h[N], e[M], w[M], ne[M], idx;
|
|||
|
|
<<<<<<< HEAD
|
|||
|
|
int dis[N]; // 最小距离数组
|
|||
|
|
=======
|
|||
|
|
int dis[N]; // 最小距离数组
|
|||
|
|
bool st[N]; // 是否在队列中
|
|||
|
|
|
|||
|
|
>>>>>>> 273b1ba54225ce58787e704d3a022dc4b01a35b0
|
|||
|
|
int stop[N]; // 站点数组
|
|||
|
|
|
|||
|
|
void add(int a, int b, int c) {
|
|||
|
|
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
|
|||
|
|
}
|
|||
|
|
// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
|
|||
|
|
void dijkstra() {
|
|||
|
|
memset(dis, 0x3f, sizeof dis); // 求最小设最大
|
|||
|
|
dis[1] = 0; // 1到自己，乘车数0
|
|||
|
|
priority_queue<PII, vector<PII>, greater<PII>> q; // 小顶堆
|
|||
|
|
q.push({0, 1}); // 1号入队列
|
|||
|
|
|
|||
|
|
while (q.size()) {
|
|||
|
|
auto t = q.top();
|
|||
|
|
q.pop();
|
|||
|
|
int u = t.second;
|
|||
|
|
<<<<<<< HEAD
|
|||
|
|
// int d = t.first; // 此处 d=t.first没有用上，经测试，其实d=dis[u]，用哪个都是一样的
|
|||
|
|
=======
|
|||
|
|
>>>>>>> 273b1ba54225ce58787e704d3a022dc4b01a35b0
|
|||
|
|
if (st[u]) continue;
|
|||
|
|
st[u] = true;
|
|||
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|||
|
|
int v = e[i];
|
|||
|
|
if (dis[v] > dis[u] + w[i]) {
|
|||
|
|
dis[v] = dis[u] + w[i];
|
|||
|
|
q.push({dis[v], v});
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
int main() {
|
|||
|
|
memset(h, -1, sizeof h); // 初始化邻接表
|
|||
|
|
cin >> m >> n; // 总共有N个车站,开通了M条单程巴士线路
|
|||
|
|
while (m--) { // m条边
|
|||
|
|
// ① 先读入第一个数字
|
|||
|
|
int cnt = 0; // cnt一定要清零
|
|||
|
|
cin >> stop[++cnt];
|
|||
|
|
char ch = getchar();
|
|||
|
|
while (ch == ' ') {
|
|||
|
|
// ② 读入其它数字
|
|||
|
|
cin >> stop[++cnt]; // 还有就继续读
|
|||
|
|
ch = getchar(); // 为下一次做准备
|
|||
|
|
}
|
|||
|
|
// 这个建图建的妙啊！
|
|||
|
|
// 通过多条边，成功映射了问题，将一趟车问题转化为多个点之间边是1问题
|
|||
|
|
for (int i = 1; i <= cnt; i++)
|
|||
|
|
for (int j = i + 1; j <= cnt; j++)
|
|||
|
|
add(stop[i], stop[j], 1);
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
dijkstra();
|
|||
|
|
if (dis[n] == INF)
|
|||
|
|
puts("NO");
|
|||
|
|
else
|
|||
|
|
printf("%d\n", dis[n] - 1);
|
|||
|
|
return 0;
|
|||
|
|
}
|