Codeforces Round #383 (Div. 1) Problem A. Arpa's loud Owf and Mehrdad's evil plan 解题报告

Codeforces Round #383 (Div. 1) Problem A. Arpa's loud Owf and Mehrdad's evil plan 解题报告

题目链接：Here！

题目大意：给你n个点之间的连接情况，问对于所有点，求一个最小的t，使得对于每一个点都有与之对应的点两点之间距离相等且为t的正整数倍。

解题思路：由于n的范围比较小，我们可以直接用floyd求出每两个点之间的最短路径，然后暴力判断每个点是否合法即可。注意每次更新答案的时候都是取lcm，在这个过程中可能会爆int，所以我用的long long。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <deque>
#define LL long long
#define INF 0x3f3f3f3f
#define PII pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))using namespace std;
int dis[105][105];void floyd(int n){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)dis[j][k]=min(dis[j][k],dis[j][i]+dis[i][k]);
}inline LL lcm(LL a,LL b){return a*b/__gcd(a,b);}int main(){int n;while(scanf("%d",&n)==1){memset(dis,INF,sizeof dis);for(int i=1;i<=n;i++){int k;scanf("%d",&k);dis[i][k]=1;}floyd(n);LL ans=1;for(int i=1;i<=n;i++){bool cg=false;LL tmp=INF;for(int j=1;j<=n;j++)if(dis[i][j]==dis[j][i]&&dis[i][j]!=INF)tmp=min(tmp,(LL)dis[i][j]),cg=true;//cout<<i<<' '<<tmp<<' '<<cg<<endl;ans=lcm(ans,tmp);if(!cg){ans=INF;break;}}printf("%dn",ans==INF?-1:ans);}return 0;
}