Link

点击打开题目链接

Problem

In Absurdistan, there are n towns (numbered 1 through n) and m bidirectional railways. There is also an absurdly simple road network — for each pair of different towns x and y, there is a bidirectional road between towns x and yif and only if there is no railway between them. Travelling to a different town using one railway or one road always takes exactly one hour.

A train and a bus leave town 1 at the same time. They both have the same destination, town n, and don’t make any stops on the way (but they can wait in town n). The train can move only along railways and the bus can move only along roads.

You’ve been asked to plan out routes for the vehicles; each route can use any road/railway multiple times. One of the most important aspects to consider is safety — in order to avoid accidents at railway crossings, the train and the bus must not arrive at the same town (except town n) simultaneously.

Under these constraints, what is the minimum number of hours needed for both vehicles to reach town n (the maximum of arrival times of the bus and the train)? Note, that bus and train are not required to arrive to the town n at the same moment of time, but are allowed to do so.

Mean

有N个城市,其中有M条铁路,如果任意两点之间没有直接相连的铁路,那么一定有直接相连的公路。现在有汽车和火车从1出发走到N,问你两辆车最晚多长时间到达N。两辆车同一时间不能到达同一点(除终点)。

Analysis

被题意坑了,也是自己没转弯过来。一直在把两种交通工具合起来作BFS,结果一直超时。

其实并没有这么难,如果从1-N有直达铁路,那么dijkstra计算汽车的最短路即可,反之亦然。

Code

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> P;
const int maxn = 410, inf = 0x3f3f3f3f;
int n, m, f[maxn][maxn], d[maxn];

int dijkstra(bool flag) {
    memset(d, inf, sizeof(d)); d[1] = 0;
    priority_queue<P, vector<P>, greater<P>> qu;
    qu.push(P(0, 1));
    while (!qu.empty()) {
        P p = qu.top(); qu.pop();
        int u = p.second;
        if (d[u] < p.first) continue;
        for(int i = 1; i <= n; ++i) {
            if(f[u][i] != flag)
                continue;
            if (d[i] > p.first + 1) {
                d[i] = p.first + 1;
                qu.push(P(d[i], i));
            }
        }
    }
    return d[n] >= inf ? -1 : d[n];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int x, y; scanf("%d%d", &x, &y);
        f[x][y] = f[y][x] = true;
    }
    printf("%d\n", dijkstra(!f[1][n]));
    return 0;
}

欢迎留言