问题
Picnic
牛打算去郊游！各区域的K(1≤K≤100)只牛在N(1≤N≤1000)个牧草地中的某个牧草地上吃草。我们把这些牧草地命名为牧草地1,2,⋯,N。
这些牧草地连接成M(1≤M≤10000)个单向的路。 (每个路的出发地和到达地都不一样。)
牛们在郊游过程中，希望在同样的牧草地上集合。但是有些牛不可能到达所有的牧草地(因为是单向道路)。请帮助牛们计算它们能在几个牧草地全部集合。
输入
第一行空格划分输入三个整数K, N, M。
第二行到K+1行，每行给出K只牛第一次吃草的位置。
K+2行到 M+K+1行，给出单向道路的信息，开始点S和结束点E。
输出
请输出所有的牛可以集合的牧草地数量。
案例输入
2 4 4
2
3
1 2
1 4
2 3
3 4
案例输出
2
案例说明
所有的牛可以在3,4的牧草地上集合。
#define MAX10000
vector<int>edge[MAX];
boolis_gone[MAX];
intcnt[MAX];
voiddfs(int w) {
int i;
is_gone[w] = 1;
cnt[w]++;
for (i = 0; i < edge[w].size(); i++) {
if (is_gone[edge[w][i]])
continue;
dfs(edge[w][i]);
}
}
int Q[MAX];
int main(){
int k, n, m;
int i, j;
int s, e;
int ans;
scanf("%d%d%d", &k, &n,&m);
for (i = 0; i < k; i++) {
scanf("%d", &Q[i]);
}
for (i = 0; i < m; i++) {
scanf("%d%d", &s,&e);
edge[s].push_back(e);
}
for (i = 0; i < k; i++) {
for (j = 1; j <= n; j++) {
is_gone[j] = 0;
}
dfs(Q[i]);
}
ans = 0;
for (i = 1; i <= n; i++) {
if (cnt[i] == k)
ans++;
}
printf("%d", ans);
return 0;}
##### 另一种实现方式############
// another solution #include <stdio.h> #include <vector> #include <algorithm> #include <queue> using namespace std; int N, M, X; vector< pair<int, int> > edges[50003]; vector< pair<int, int> > rev_edges[50003]; vector<int> dijkstra(vector< pair<int, int> > edges[]) { priority_queue<pair<int, int> > Q; vector<int> table(N, 100000000); vector<bool> visit(N, false); table[X] = 0; Q.push(make_pair(0, X)); while (!Q.empty()) { pair<int, int> now = Q.top(); Q.pop(); if (visit[now.second]) { continue; } visit[now.second] = true; for (int i = 0; i < edges[now.second].size(); i++) { int next = edges[now.second][i].first; int cost = edges[now.second][i].second; if (table[next] > table[now.second] + cost) { table[next] = table[now.second] + cost; Q.push(make_pair(-table[next], next)); } } } return table; } int main() { scanf("%d %d %d", &N, &M, &X); X--; for (int i = 0; i < M; i++) { int s, e, c; scanf("%d %d %d", &s, &e, &c); s--; e--; edges[s].push_back(make_pair(e, c)); rev_edges[e].push_back(make_pair(s, c)); } vector<int> D1 = dijkstra(edges); vector<int> D2 = dijkstra(rev_edges); int ret = 0; for (int i = 0; i < N; i++) { if (ret < D1[i] + D2[i]) { ret = D1[i] + D2[i]; } edges[i].clear(); rev_edges[i].clear(); } printf("%d\n", ret); return 0; }