Untitled
unknown
plain_text
7 months ago
1.5 kB
1
Indexable
Never
#include <bits/stdc++.h> using namespace std; typedef long long int ll; #define endl "\n" const double PI = 3.14159265358979; const ll INF = 1e9 + 7; const ll MOD = 1e9 + 7; const ll nax = 2505; const int LOG = 25; vector<int> dijkstra(int src, int n, vector<pair<int, int> > adj[]) { vector<int> dist(n + 1, INF); vector<bool> visited(n + 1, false); deque<int> dq; dist[src] = 0; dq.push_back(src); while(!dq.empty()) { int current = dq.front(); dq.pop_front(); if (visited[current]) continue; visited[current] = true; for (auto neigh: adj[current]) { if (dist[neigh.first] > dist[current] + neigh.second) { dist[neigh.first] = dist[current] + neigh.second; } if (neigh.second == 0) { dq.push_front(neigh.first); } else { dq.push_back(neigh.first); } } } return dist; } void solve() { int n, m; cin >> n >> m; vector<pair<int, int> > adj[n + 1]; for (int i = 1; i <= m; i++) { int x, y; cin >> x >> y; if (x != y) { adj[x].push_back({y, 0}); adj[y].push_back({x, 1}); } } vector<int> dist = dijkstra(1, n, adj); cout << (dist[n] == INF ? -1 : dist[n]) << endl; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t; cin >> t; while(t--) solve(); return 0; }
Leave a Comment