51nod1649 齐头并进 (思维，最短路)

51nod1649 齐头并进 (思维，最短路)

原题链接：.html#!problemId=1649

思路：因为所有没有地铁的地方都有公路，也就是说公交车和火车其中的某一个都可以一小时到达，我们只需要求另一个的最短路即可，实现上用邻接矩阵方便一点

AC代码：

#include<bits/stdc++.h>
using namespace std;const int MAXN = 405;
const int INF = 0x3f3f3f3f;
int n, m, u, v;
int cnt, head[MAXN], mp[MAXN][MAXN], d[MAXN];
bool vis[MAXN];
void dijkstra() {memset(vis, false, sizeof(vis));for (int i = 1; i <= n; i++)d[i] = INF;d[1] = 0;for (int i = 0; i < n; i++) {int m = INF, x = -1;for (int y = 1; y <= n; y++)if (!vis[y] && d[y] < m)m = d[x = y];if (x == -1)continue;vis[x] = true;for (int y = 1; y <= n; y++) {if (mp[x][y] == 1 && d[y] > d[x] + mp[x][y]) {d[y] = d[x] + mp[x][y];}}}
}int main() {scanf("%d %d", &n, &m);memset(mp, -1, sizeof(mp));for (int i = 1; i <= n; i++) {mp[i][i] = 0;}for (int i = 0; i < m; i++) {scanf("%d %d", &u, &v);mp[u][v] = mp[v][u] = 1;}if (mp[1][n] == 1) {for (int i = 1; i <= n; i++) {for (int j = i + 1; j <= n; j++) {mp[i][j] = -mp[i][j];mp[j][i] = -mp[j][i];}}}dijkstra();printf("%dn", d[n] == INF ? -1 : d[n]);return 0;
}