andyli

题解 UVA11374 【Airport Express】
因为商业线只能坐一站,所以可以枚举坐的是哪一站,比较所有可能性下的最优解。如果可以在$O(1)$的时间内计算出每种...
扫描右侧二维码阅读全文
24
2019/06

题解 UVA11374 【Airport Express】

因为商业线只能坐一站,所以可以枚举坐的是哪一站,比较所有可能性下的最优解。如果可以在$O(1)$的时间内计算出每种方案对应的最优方案,整个问题就可以在$O(K)$的时间内得到解决。
假设我们用商业线车票从车站$a$坐到车站$b$,则从起点到$a$、从$a$到终点这两部分路线对于“经济线网络”来说都应该是最短路。换句话说,我们只需要从起点开始、到终点结束坐两次单源最短路,记录下从起点到每一个点$x$的最短时间$f(x)$和从每个点$x$到终点的最短时间$g(x)$,则总时间为$f(a)+T(a,b)+g(b)$,其中$T(a,b)$为从$a$坐一站商业线到达$b$的时间。
算上预处理时间$O(m\log n)$,本算法的总时间复杂度为$O(m\log n+k)$。
代码如下:

#include <cstring>
#include <vector>
#include <cstdio>
#include <queue>
#include <stack>
using namespace std;
const int INF = 0x3f3f3f3f, maxn = 1000005;

struct Edge
{
    int next, to, dist;
    Edge() {}
    Edge(int u, int v, int d) : next(u), to(v), dist(d) {}
};

class Dijkstra
{
  public:
    struct HeapNode
    {
        int d, u;
        bool operator<(const HeapNode &rhs) const
        {
            return d > rhs.d;
        }
    };
    int n, m;
    vector<Edge> edges;
    bool done[maxn];
    int d[maxn], head[maxn];
    int p[maxn];
    void init(int n)
    {
        this->n = n;
        edges.clear();
        memset(head, -1, sizeof(head));
    }
    void AddEdge(int from, int to, int dist)
    {
        edges.emplace_back(head[from], to, dist);
        head[from] = edges.size() - 1;
    }
    void dijkstra(int s)
    {
        priority_queue<HeapNode> Q;
        for (int i = 1; i <= n; i++)
            d[i] = INF;
        d[s] = 0;
        memset(done, 0, sizeof(done));
        memset(p, 0, sizeof(p));
        Q.push((HeapNode){0, s});
        while (!Q.empty())
        {
            HeapNode x = Q.top();
            Q.pop();
            int u = x.u;
            if (done[u])
                continue;
            done[u] = true;
            for (int v = head[u]; ~v; v = edges[v].next)
            {
                if (d[edges[v].to] > d[u] + edges[v].dist)
                {
                    d[edges[v].to] = d[u] + edges[v].dist;
                    p[edges[v].to] = u;
                    Q.push((HeapNode){d[edges[v].to], edges[v].to});
                }
            }
        }
    }
};

int diss[maxn], ps[maxn], cnt;
Edge edges[maxn << 2];

int main()
{
    int N, S, E, M, kase = 0;
    while (scanf("%d%d%d", &N, &S, &E) == 3)
    {
        if (kase++)
            printf("\n");
        Dijkstra dij;
        dij.init(N);
        scanf("%d", &M);
        while (M--)
        {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            dij.AddEdge(u, v, w);
            dij.AddEdge(v, u, w);
        }
        scanf("%d", &M);
        cnt = 0;
        for (int i = 1; i <= M; i++)
        {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            edges[++cnt] = Edge(u, v, w);
            edges[++cnt] = Edge(v, u, w);
        }
        dij.dijkstra(S);
        memcpy(diss, dij.d, sizeof(dij.d));
        memcpy(ps, dij.p, sizeof(dij.p));
        dij.dijkstra(E);
        int maxt = diss[E], used = 0;
        for (int i = 1; i <= cnt; i++)
            if (maxt > diss[edges[i].next] + edges[i].dist + dij.d[edges[i].to])
                maxt = diss[edges[i].next] + edges[i].dist + dij.d[edges[i].to], used = i;
        if (used)
        {
            stack<int> st;
            int u = edges[used].next;
            while (u)
            {
                st.push(u);
                u = ps[u];
            }
            while (!st.empty())
                printf("%d ", st.top()), st.pop();
            u = edges[used].to;
            while (u != E)
            {
                printf("%d ", u);
                u = dij.p[u];
            }
            printf("%d\n%d\n%d\n", E, edges[used].next, maxt);
        }
        else
        {
            int u = S;
            while (u != E)
            {
                printf("%d ", u);
                u = dij.p[u];
            }
            printf("%d\nTicket Not Used\n%d\n", E, maxt);
        }
    }
    return 0;
}
Last modification:June 25th, 2019 at 11:30 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment