AcWing 920. 两种建图方式
原题链接
中等
作者:
染指年华
,
2024-07-25 18:06:16
,
所有人可见
,
阅读 8
- 思路与代码
- 对于这种每一行不限定个数的输入,我们使用$strinstream$类
- 法一:建立多条路径
- 我们先不考虑换乘,我们先求起点到终点,需要坐几辆车,那么换乘次数就是车辆数减$1$
- 对于一条路径$1→3→7→4$
- 那么$1→3,1→7,1→4,3→7,3→4, 7→4$的乘车数目都是$1$,因此将这些边建图
- 那么起点到终点的车辆数就是在图上求起点到终点的边权均为$1$的最短路
- 答案就是最短路$-1$
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using PII = pair<int, int>;
using PDI = pair<double, int>;
using PLI = pair<ll, int>;
using PLL = pair<ll, ll>;
using PSI = pair<string, int>;
using PSS = pair<string, string>;
using PDD = pair<double, double>;
template <typename T> using max_heap = priority_queue<T>;
template <typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
#define all(x) x.begin(), x.end()
#define endl '\n'
void solve() {
int m, n; cin >> m >> n;
const int inf = 0x3f3f3f3f;
vector<vector<PII>> g(n + 1);
for (int i = 0; i <= m; i++) {
string t; getline(cin, t);
vector<int> arr;
stringstream s; s << t;
int x;
while (s >> x) arr.emplace_back(x);
for (int i = 0; i < arr.size(); i++) {
for (int j = i + 1; j < arr.size(); j++) g[arr[i]].emplace_back(arr[j], 1);
}
}
function<int()> bfs = [&]() -> int {
queue<int> q;
vector<bool> vis(n + 1);
vector<int> dist(n + 1, inf);
dist[1] = 0;
q.emplace(1);
while (q.size()) {
auto cur = q.front(); q.pop();
for (auto &x : g[cur]) {
if (dist[cur] + x.second < dist[x.first]) {
dist[x.first] = dist[cur] + x.second;
q.emplace(x.first);
}
}
}
return dist[n];
};
int ans = bfs();
if (ans == inf) cout << "NO" << endl;
else cout << ans - 1 << endl;
return ;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t; t = 1;
while (t--) solve();
return 0;
}
- 法二:建立单条路径与线路$id$
- 根据每一条线路所给,将相邻两项进行单向连接,同时记录是第几条线路,同一条线路的数值相同
- 对于一条路径$1→3→7→4$,假设是第$3$条线路,那么记录$1→3, 3→7, 7→4$,同时他们的线路$id$为$3$
- 那么从起点到终点,如果父节点线路与子节点线路相同,那么子节点换乘次数与父节点相同,否则为父节点换乘次数$+1$
- 注意,在进行$bfs$求解过程中,
- 如果子节点被更新过且线路一致且父节点等于子节点换乘次数,那么仍要将子节点加入队列
- 如果子节点被更新过且线路不一致且父节点等于子节点换乘次数$+1$,那么仍要将子节点加入队列
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using PII = pair<int, int>;
using PDI = pair<double, int>;
using PLI = pair<ll, int>;
using PLL = pair<ll, ll>;
using PSI = pair<string, int>;
using PSS = pair<string, string>;
using PDD = pair<double, double>;
template <typename T> using max_heap = priority_queue<T>;
template <typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
#define all(x) x.begin(), x.end()
#define endl '\n'
void solve() {
int m, n; cin >> m >> n;
const int inf = 0x3f3f3f3f;
vector<vector<PII>> g(n + 1);
for (int i = 0; i <= m; i++) {
string t; getline(cin, t);
stringstream s; s << t;
int st, x; s >> st;
while (s >> x) g[st].emplace_back(x, i), st = x;
}
function<int()> bfs = [&]() -> int {
queue<PII> q;
vector<int> dist(n + 1, inf);
dist[1] = 0;
q.emplace(1, -1);
while (q.size()) {
auto cur = q.front(); q.pop();
int root = cur.first, fa_line = cur.second;
for (auto &[node, line] : g[root]) {
if (fa_line == -1 || fa_line == line) {
if (dist[root] <= dist[node]) {
dist[node] = dist[root];
q.emplace(node, line);
}
} else {
if (dist[root] + 1 <= dist[node]) {
dist[node] = dist[root] + 1;
q.emplace(node, line);
}
}
}
}
return dist[n];
};
int ans = bfs();
if (ans == inf) cout << "NO" << endl;
else cout << ans << endl;
return ;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t; t = 1;
while (t--) solve();
return 0;
}