読者です 読者をやめる 読者になる 読者になる

AOJ 0144 Packet Transportation

404 Not Found

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;
	}
}