BFSで解いて、学校に出すレポートそれで書いた後にワーシャルフロイド法で解けるじゃんって気づいた。死しかない。
辺の重みが1均一。
BFSソース
#include <iostream> #include <queue> #include <map> #include <climits> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) typedef pair<int,int> NODE; #define pos first #define distance second int n; bool info[100][100]; int bfs(int s,int d){ queue<NODE> Q; bool done[100]={false}; Q.push( make_pair(s,0) ); while( !Q.empty() ){ NODE now = Q.front(); Q.pop(); done[now.pos] = true; if(now.pos == d){ return now.distance; } for(int next=0;next<n;next++){ if(info[now.pos][next] && !done[next]){ Q.push( make_pair(next,now.distance+1) ); } } } return INT_MAX; } int main(){ int r,k,t,p,s,d,v; cin >> n; for(int i=0;i<n;i++){ cin >> r >> k; r--; for(int j=0;j<k;j++){ cin >> t; t--; info[r][t] = true; } } cin >> p; for(int i=0;i<p;i++){ cin >> s >> d >> v; s--;d--; if(v > bfs(s,d) )cout << bfs(s,d)+1 << endl; else cout << "NA" << endl; } }
WF
#include <iostream> #include <queue> #include <climits> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) int main(){ int n,r,k,t,p,s,d,v; int wf[100][100]; rep(i,100)rep(j,100)wf[i][j] = 1<<21; cin >> n; for(int i=0;i<n;i++){ cin >> r >> k; r--; for(int j=0;j<k;j++){ cin >> t; t--; wf[r][t] = 1; } } rep(k,n)rep(i,n)rep(j,n)wf[i][j]=min(wf[i][j],wf[i][k]+wf[k][j]); cin >> p; for(int i=0;i<p;i++){ cin >> s >> d >> v; s--;d--; if(v > wf[s][d] )cout << wf[s][d]+1 << endl; else cout << "NA" << endl; } }