UVa12319 Edgetown's Traffic Jams

概要
与えられた無向グラフを、与えられた有向グラフ（片方向の向きを削ったもの）にしたとき、有向グラフの任意の二点の距離は A*x+B（xは無向グラフの距離）以内に収まるかどうか判定せよ。

解法
ワーシャルフロイドをそれぞれのグラフについて行った後、任意の二点について条件を確かめる。

#include <bits/stdc++.h>

using namespace std;

int tbl[100][100];
int ubl[100][100];

int const INF = 1<<26;

inline int toInt(string str) {
  stringstream ss(str);
  int x; ss >> x;
  return x;
}

vector<int> getList() {
  string str;
  getline(cin, str);
  stringstream ss(str);
  
  vector<int> ret;
  while(ss >> str) {
    ret.push_back(toInt(str)-1);
  }
  return ret;
}

int main() {
  
  int N;
  while(cin >> N && N) {
    cin.ignore();
    fill(tbl[0], tbl[0]+100*100, INF);
    for(int i=0; i<N; i++) {
      vector<int> vec(getList());
      for(int j=1; j<(int)vec.size(); j++) {
	tbl[vec[0]][vec[j]] = 1;
      }
    }
    
    fill(ubl[0], ubl[0]+100*100, INF);
    for(int i=0; i<N; i++) {
      vector<int> vec(getList());
      for(int j=0; j<(int)vec.size(); j++) {
	ubl[vec[0]][vec[j]] = 1;
      }
    }
    
    int A, B;
    cin >> A >> B;
    
    for(int k=0; k<N; k++)
      for(int i=0; i<N; i++)
	for(int j=0; j<N; j++)
	  tbl[i][j] = min(tbl[i][j], tbl[i][k]+tbl[k][j]);
    
    for(int k=0; k<N; k++)
      for(int i=0; i<N; i++)
	for(int j=0; j<N; j++)
	  ubl[i][j] = min(ubl[i][j], ubl[i][k]+ubl[k][j]);
    
    for(int i=0; i<N; i++) {
      for(int j=0; j<N; j++) {
	if(tbl[i][j]*A+B < ubl[i][j]) {
	  cout << "No" << endl;
	  goto EXIT;
	}
      }
    }
    
    cout << "Yes" << endl;
    
  EXIT:;
  }
  
  return 0;
}