AcWing
4074. 铁路与公路
floyd算法，模板。一个可以注意到的事实是，无论是公路还是铁路，从起点到终点一定有一条路线，所以从起点到终点的最长时间即为另一条路线的时间(如果存在)。即，$res = \max{(route_t, route_g)}$，其中，$route_t = 1\quad or \quad route_g = 1$. 路线的时间可以通过floyd/dijkstra/SPFA求得。
Floyd:
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 410, INF = 0x3f3f3f3f;
int t[N][N], g[N][N];
int floyd(int d[][N]){
if(d[1][N] == 1) return 1;
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(i != j && d[i][k] + d[k][j] < d[i][j]){
d[i][j] = d[i][k] + d[k][j];
}
}
}
}
return d[1][n];
}
int main(){
cin >> n >> m;
memset(t, INF, sizeof t);
memset(g, INF, sizeof g);
while(m--){
int u, v;
cin >> u >> v;
t[u][v] = t[v][u] = 1;
}
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(i != j && t[i][j] != 1) g[i][j] = 1;
int res = max(floyd(t), floyd(g));
if(res >= INF) res = -1;
cout << res << endl;
return 0;
}
spfa:
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 410, M = 200010, INF = 0x3f3f3f3f;
int h1[N], h2[N], e[M], ne[M], idx;
int t[N][N];
int dist[N];
bool visited[N];
void add(int h[], int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int spfa(int h[], bool flag){
if(flag && t[1][n] || !flag && !t[1][n]) return 1;
memset(visited, false, sizeof visited);
memset(dist, 0x3f, sizeof dist);
queue<int> q;
q.push(1);
visited[1] = 1;
dist[1] = 0;
while(!q.empty()){
int top = q.front();
visited[top] = 0;
q.pop();
for(int i = h[top]; ~i; i = ne[i]){
int j = e[i];
if(dist[j] > dist[top] + 1){
dist[j] = dist[top] + 1;
if(!visited[j]){
q.push(j);
visited[j] = 1;
}
}
}
}
// for(int i = 1; i <= n; i++) cout << dist[i] << ' ';
// cout << endl;
return dist[n];
}
int main(){
memset(h1, -1, sizeof h1);
memset(h2, -1, sizeof h1);
cin >> n >> m;
while(m--){
int u, v;
cin >> u >> v;
t[u][v] = t[v][u] = 1;
add(h1, u, v);
add(h1, v, u);
}
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(!t[i][j] && i != j){
add(h2, i, j);
add(h2, j, i);
}
int res = max(spfa(h1, 1), spfa(h2, 0));
if(res >= INF) res = -1;
cout << res << endl;
return 0;
}