PKU演習問メモ

No. 問題名 問題の種類および解法 難易度
3263 Tallest Cow 貪欲法 ★★★☆☆
3615 Cow Hurdles ワーシャルフロイド ★★☆☆☆

3263 Tallest Cow

問題概要
解法
ソースコード
int n,I,H,r;
int h[10000]; pi in[10000];
int main()
{
  scanf("%d%d%d%d",&n,&I,&H,&r);
  rep(i,n)h[i]=H;

  int a,b;
  rep(i,r){
    scanf("%d%d",&a,&b);
    if(a>b)swap(a,b);
    in[i].first=a-1; in[i].second=b-1;
  }
  sort(in,in+r); r=unique(in,in+r)-in;

  rep(i,r)for(int j=in[i].first+1;j<in[i].second;j++)h[j]--;
  rep(i,n)printf("%d\n",h[i]);
  return 0;
}

3615 Cow Hurdles

問題概要
解法
ソースコード
int n,m,t;
int h[300][300];

int main()
{
  scanf("%d%d%d",&n,&m,&t);
  rep(i,n)rep(j,n)h[i][j]=i!=j?inf:0;

  int a,b,c;
  rep(i,m){
    scanf("%d%d%d",&a,&b,&c);
    h[a-1][b-1]=c;
  }
  rep(k,n)rep(i,n)rep(j,n)h[i][j]=min(h[i][j],max(h[i][k],h[k][j]));

  rep(i,t){
    scanf("%d%d",&a,&b); a--,b--;
    printf("%d\n",h[a][b]==inf?-1:h[a][b]);
  }
  return 0;
}