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