51nod 1649 齐头并进 (dijkstra)

51nod 1649 齐头并进 (dijkstra)

两次最短路找最大值；

#pragma GCC optimize(2)#include <bits/stdc++.h>#define maxn 405typedef long long ll;using namespace std;ll a[maxn][maxn];
ll b[maxn][maxn];
ll mo = 1e18;
ll dis[maxn];
ll flag[maxn],mi,n,k;
void dfs1(ll be)
{for(int i = 1; i <= n; i ++){dis[i] = 1e18;}dis[be] = 0;//flag[be] = 1;for(int i = 1; i <= n; i ++){mi = mo;for(int j = 1; j <= n; j ++){if(!flag[j] && dis[j] < mi){mi = dis[j];k = j;}}if(mi == mo)break;flag[k] = 1;for(int j = 1; j <= n; j ++){if(!flag[j] && dis[j] > dis[k] + a[k][j]){dis[j] = dis[k] + a[k][j];}}}
}void dfs2(ll be)
{for(int i = 1; i <= n; i ++){dis[i] = 1e18;}dis[be] = 0;//flag[be] = 1;for(int i = 1; i <= n; i ++){mi = mo;for(int j = 1; j <= n; j ++){if(!flag[j] && dis[j] < mi){mi = dis[j];k = j;}}if(mi == mo)break;flag[k] = 1;for(int j = 1; j <= n; j ++){if(!flag[j] && dis[j] > dis[k] + b[k][j]){dis[j] = dis[k] + b[k][j];}}}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll m;cin >> n >> m;for(int i = 1; i <= n; i ++){for(int j = 1; j <= n ; j ++){a[i][j] = 1e18;}}for(int i = 1; i <= m ; i ++){ll x,y;cin >> x >> y;a[x][y] = 1;a[y][x] = 1;}for(int i = 1; i <= n; i ++){for(int j = 1; j <= n ; j ++){b[i][j] = 1e18;}}for(int i = 1; i <= n; i ++){for(int j = 1; j <= n; j ++){if(i != j && a[i][j] == mo){b[i][j] = 1;b[j][i] = 1;}}}dfs1(1);ll m1 = dis[n];if(m1 == mo)cout << -1 << endl;else{memset(flag,0,sizeof(flag));dfs2(1);k = 0;ll m2 = dis[n];if(m2 == mo)cout << -1 << endl;else{cout << max(m1,m2) << endl;}}return 0;
}