P2296 寻找道路

#include <bits/stdc++.h>
using namespace std;
const int maxn = 10005;
set<int> to[maxn];
queue<int> q;int s, t;int n, m;set<int> to2[maxn];
int dist[maxn], used[maxn], dist2[maxn];
int main() {
// freopen("input.in", "r", stdin);
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
to[x].insert(y);
to2[y].insert(x);
}
cin >> s >> t;
//-----------------
q.push(t);
memset(dist2, -1, sizeof(dist2));
dist2[t] = 0;
memset(used, 0, sizeof(used));
used[t] = 1;
while(!q.empty()) {
int x = q.front();
q.pop();
set<int>::iterator it;
for(it = to2[x].begin(); it != to2[x].end(); it++) {
if(!used[*it]) {
dist2[*it] = dist2[x] + 1;
used[*it] = 1;
q.push(*it);
}
}
}
memset(used, 0, sizeof(used));
for(int i = 1; i <= n; i++) {
if(dist2[i] == -1) {
set<int>::iterator it;
for(it = to2[i].begin(); it!=to2[i].end(); it++) {
used[*it] = 1;
}
}
}
//-----------------
memset(dist, -1, sizeof(dist));
dist[s] = 0;
q.push(s);
used[s] = 1;
while(!q.empty()) {
int x = q.front();
q.pop();
set<int>::iterator it;
for(it = to[x].begin(); it != to[x].end(); it++) {
if(!used[*it]) {
dist[*it] = dist[x] + 1;
used[*it] = 1;
q.push(*it);
}
}
}
cout << dist[t];
}
上一篇:Python判断是否是数字(无法判断浮点数)(已解决)


下一篇:javascript 获取元素样式的方法