首页 > 代码库 > Codeforces 601A
Codeforces 601A
#include <bits/stdc++.h> using namespace std; #define maxn 411 #define INF 11111 int a1[maxn][maxn], a2[maxn][maxn]; int n, m; int d[maxn]; bool vis[maxn]; int dij (int a[maxn][maxn]) { for (int i = 1; i <= n; i++) { d[i] = INF; vis[i] = 0; } d[1] = 0; for (int j = 1; j <= n; j++) { int k = -1; int Min = INF; for (int i = 1; i <= n; i++) { if (!vis[i] && d[i] < Min) { Min = d[i]; k = i; } } if (k == -1) break; vis[k] = 1; for (int i = 1; i <= n; i++) { if (!vis[i]) d[i] = min (d[i], d[k]+a[k][i]); } } return d[n]; } int main () { scanf ("%d%d", &n, &m); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { a1[i][j] = a2[i][j] = INF; } } int u, v; for (int i = 1; i <= m; i++) { scanf ("%d%d", &u, &v); a1[u][v] = a1[v][u] = 1; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) continue; if (a1[i][j] == INF) a2[i][j] = 1; } } int ans1 = dij (a1); int ans2 = dij (a2); if (ans1 >= INF || ans2 >= INF) cout << "-1" << endl; else cout << max (ans1, ans2) << endl; return 0; }
Codeforces 601A
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。