牛客算法周周练5 D 小雨坐地铁

题目

题目链接

分析

这样的题目很容易想到 分层图 和 最短路, 而这类型的题目, 重点主要在建图上.

分层图中, 每一层自然是每一条地铁线路, 这个好说. 那层与层之间, 怎样建立关系呢?
可以这样理解吧, 将一个站台分成不同区域, 一个中转区, 多个(如果有的话)不同线路地铁的站台.
那么接下来就好说了.

从这个中转区到这一点其他站台, 都要交相应的车费 , 而从每个站台下车到中转区, 是不花钱的.
于是, 可以在额外的一层图中, 建立 n 个虚点, 即 n 个中转区, 连接该点所有的站台.
至此, 这个问题就解决了.

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
#include <utility>

using namespace std;

const int SIZE = 1e6;
const int INF = 0x3f3f3f3f;

struct Edge
{
    int end;
    int weight;
    int next;
};

Edge edge[SIZE];
int head[SIZE];
int edgestamp;

int dis[SIZE];
bool flag[SIZE];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > heap;

void addEdge(int u, int v, int w);
void dijkstra(int source);
int main()
{
    int n, m, s, t;
    int a, b, c;
    int u, v;

//    freopen("cpp.in", "r", stdin);

    scanf("%d %d %d %d", &n, &m, &s, &t);
    for (register int i = 1; i <= m; i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        for (register int j = 1; j <= c; j++)
        {
            scanf("%d", &v);
            if (j > 1)
            {
                addEdge((i - 1) * n + u, (i - 1) * n + v, b);
                addEdge((i - 1) * n + v, (i - 1) * n + u, b);
            }
            addEdge((i - 1) * n + v, m * n + v, 0);
            addEdge(m * n + v, (i - 1) * n + v, a);
            u = v;
        }
    }
    dijkstra(m * n + s);
    if (dis[m * n + t] < INF)
        printf("%d\n", dis[m * n + t]);
    else
        printf("-1\n");

//    fclose(stdin);
    return 0;
}    
void addEdge(int u, int v, int w)
{
    edge[++edgestamp].end = v;
    edge[edgestamp].weight = w;
    edge[edgestamp].next = head[u];
    head[u] = edgestamp;
}
void dijkstra(int source)
{
    int u, v, w;

    memset(dis, 0x3f, sizeof(dis));
    memset(flag, false, sizeof(flag));
    dis[source] = 0;

    heap.push(make_pair(dis[source], source));
    while (!heap.empty())
    {
        u = heap.top().second;
        heap.pop();
        if (flag[u])
            continue;
        flag[u] = true;
        for (register int i = head[u]; i != 0; i = edge[i].next)
        {
            v = edge[i].end;
            w = edge[i].weight;

            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                if (!flag[v])
                    heap.push(make_pair(dis[v], v));
            }
        }
    }
}