1 条题解
-
0
#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 200'000; const int MAXX = 1'000'000'000; const int INF = MAXN + MAXN * MAXX; int n, m, x; vector<pair<int, int>> e[MAXN * 2 + 5]; vector<pair<int, int>> ee[MAXN * 2 + 5]; int dis[MAXN * 2 + 5]; bool vis[MAXN * 2 + 5]; priority_queue<pair<int, int>> pq; signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> x; for (int i = 1; i <= n; i++) { e[i].push_back(make_pair(i + n, x)); e[i + n].push_back(make_pair(i, x)); } for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; e[u].push_back(make_pair(v, 1)); e[v + n].push_back(make_pair(u + n, 1)); } for (int i = 1; i <= n + n; i++) dis[i] = INF; dis[1] = 0; pq.push(make_pair(-0, 1)); while (!pq.empty()) { int u = pq.top().second; pq.pop(); if (vis[u]) continue; vis[u] = true; for (int i = 0; i < e[u].size(); i++) { int v = e[u][i].first; int w = e[u][i].second; if (dis[u] + w < dis[v]) { dis[v] = dis[u] + w; pq.push(make_pair(-dis[v], v)); } } } cout << min(dis[n], dis[n + n]); return 0; }
- 1
信息
- ID
- 1828
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 25
- 已通过
- 11
- 上传者