1 条题解
-
1
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> #include<cstdlib> using namespace std; int n,s1,s2; int dx[55][55],dn[55][55]; int main() { scanf("%d%d%d",&n,&s1,&s2); char a[60]; for(int i=1;i<=n;i++){ scanf("%s",a); for(int j=0;j<strlen(a);j++){ if(a[j]=='=' || i==j+1){ dn[i][j+1]=0;dx[i][j+1]=0; } else if(a[j]=='+') { dx[i][j+1]=2; dn[i][j+1]=1; //i-j<=2; i-j>=1; }else if(a[j]=='-'){ dx[i][j+1]=-1; dn[i][j+1]=-2; //i-j<=-1;i-j>=-2; }else { dx[i][j+1]=2; dn[i][j+1]=-2; //i-j<=2; i-j>=-2; } } } for(int k=1;k<=n;k++) //Floyd for(int i=1;i<=n;i++) { if(i==k) continue; for(int j=1;j<=n;j++){ if(i==k || i==j) continue; dx[i][j]=min(dx[i][j],dx[i][k]+dx[k][j]);//上界求最短路 dn[i][j]=max(dn[i][k]+dn[k][j],dn[i][j]);//下界求最长路 } } int c1=0,c2=0,c3=0; for(int i=1;i<=n;i++){ //暴力枚举所有可能性 if(i==s1 || i==s2) continue; for(int j=1;j<i;j++){ if(j==s1 || j==s2) continue; if(dn[s1][i]>dx[j][s2] || dn[s2][i]>dx[j][s1]) c1++; //s1-i的最小值大于j-s2的最大值==>s1+s2>i+j if(dn[i][s1]>dx[s2][j] || dn[i][s2]>dx[s1][j]) c3++; //同理:i-s1>s2-j ==> i+j>s1+s2 if((dn[s1][i]==dx[s1][i] && dn[j][s2]==dx[j][s2] && dn[s1][i]==dn[j][s2]) || (dn[s1][j]==dx[s1][j] && dn[i][s2]==dx[i][s2] && dn[s1][j]==dn[i][s2])) c2++; //关系确定且满足的点 } } printf("%d %d %d",c1,c2,c3); return 0; }
- 1
信息
- ID
- 1422
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 6
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者