分层图+最短路

题目分析

题目传送门——小雨坐地铁

ps：刚刚开始看这个题目的时候，看完一遍不理解，再看一遍还是不理解，于是冷静一波~发现这个题目真的很复杂！！！
题目是求最短路，最短路可以参考我的另外一篇博客快速理解最短路径算法

对于这个题目而言，我们需要去做出一个分层图出来，因为地铁线之间有交叉，所以在存储完地铁线之后，我们需要对建立一个超级源点，并且规定，从地铁站到超级源点需要不需要花费，而从超级源点到地铁站需要花费，这就相当于一个中转站一样，我们通过中转站去下一个地铁当然需要花费，超级源点相当于一条虚拟的地铁站，该线上有所有的地铁站虚点。

分层图就是一层一层的，这样我们就可以知道当前节点的位置坐标，就相当于一个二维数组，不同的是这个二维数组存在三维空间中

spfa+链式前向星

spfa算法由于也是用队列实现的，所以它的代码和BFS代码很像~~

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
int cnt, vis[maxn], dis[maxn], head[maxn], a[maxn], b[maxn];
struct node //结构体存储边的信息，起点，终点，边权，下一个节点
{
   
	int  v, w, next;
} e[maxn];

void add(int u, int v, int w) //链式前向星存图，每次加边都放在头结点的后面，降低时间复杂度
{
   
	e[++cnt].v = v;
	e[cnt].w = w;
	e[cnt].next = head[u];
	head[u] = cnt;
}

queue<int> q;
void spfa(int x)
{
   
	memset(dis, inf, sizeof(dis)); //初始化
	memset(vis, 0, sizeof(vis));
	vis[x] = 1; //标记该节点已经使用
	dis[x] = 0; //该节点到自己的距离为0
	q.push(x);	//放入队列
	while (!q.empty())
	{
   
		int u = q.front();
		q.pop();
		vis[u] = 0;								 //出队
		for (int i = head[u]; ~i; i = e[i].next) //遍历该节点所有的邻接点
		{
   
			int v = e[i].v;				  //后继节点
			if (dis[v] > dis[u] + e[i].w) //松弛操作
			{
   
				dis[v] = dis[u] + e[i].w;
				if (!vis[v]) //判断该节点是否遍历过
				{
   
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
}
int main()
{
   
	int n, m, s, t, sum, x, last;
	cnt = 0;
	scanf("%d%d%d%d", &n, &m, &s, &t);
	memset(head, -1, sizeof(head));
	for (int i = 1; i <= m; ++i)
	{
   
		scanf("%d%d%d", &a[i], &b[i], &sum);
		for (int j = 1; j <= sum; ++j)
		{
   
			scanf("%d", &x);
			if (j != 1) //第一个地铁站因为前面为空，所以直接和超级源点相连接，其余节点不仅要和超级源点链接，还要和上一个节点连接
			{
   
				add((i - 1) * n + x, (i - 1) * n + last, b[i]); //加边操作从当前节点到上一个节点需要花费b[i]
				add((i - 1) * n + last, (i - 1) * n + x, b[i]); //由于是无向图，所有从上一个节点到当前节点需要的花费也是b[i]
			}
			add((i - 1) * n + x, n * m + x, 0);	   //地铁站到超级源点不需要花费
			add(n * m + x, (i - 1) * n + x, a[i]); //超级源点到地铁站需要花费a
			last = x;							   //储存上一个地铁站
		}
	}
	spfa(n * m + s); //开始跑spfa
	if (dis[n * m + t] == inf)
		printf("-1\n");
	else
		printf("%d\n", dis[n * m + t]);
	return 0;
}

dijkstra+链式前向星

#include <bits/stdc++.h>
#include <queue>
using namespace std;
const int maxn = 1100;
int head[maxn * maxn], cnt, m, n, dis[maxn * maxn];
struct node
{
   
    bool operator()(int x, int y)
    {
   
        return dis[x] > dis[y];
    }
};
priority_queue<int, vector<int>, node> q;
struct edge
{
   
    int nx, to, w;
} edge[maxn * maxn * 2];
void add(int u, int v, int w)
{
   
    edge[++cnt].nx = head[u];
    edge[cnt].to = v;
    edge[cnt].w = w;
    head[u] = cnt;
}
void dijkstra(int s) //最短路算法
{
   
    dis[s] = 0;
    q.push(s);
    while (!q.empty())
    {
   
        int u = q.top();
        q.pop();
        for (int i = head[u]; ~i; i = edge[i].nx)
        {
   
            int v = edge[i].to;
            if (dis[v] > dis[u] + edge[i].w)
            {
   
                dis[v] = dis[u] + edge[i].w;
                q.push(v);
            }
        }
    }
}
int main()
{
   
    memset(dis, 0x3f3f3f3f, sizeof(dis));
    memset(head, -1, sizeof(head));
    int s, t;
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; i++)
    {
   
        int a, b, c;
        cin >> a >> b >> c;
        int last = -1; //记录上一站
        for (int j = 1; j <= c; j++)
        {
   
            int x;
            cin >> x;
            if (j != 1)
            {
   
                add((i - 1) * n + x, (i - 1) * n + last, b); //站与站之间花费b
                add((i - 1) * n + last, (i - 1) * n + x, b);
            }
            add((i - 1) * n + x, m * n + x, 0); //每一层到最后一层花费为0
            add(m * n + x, (i - 1) * n + x, a); //最后一层去上面层花费a
            last = x;
        }
    }
    dijkstra(s + m * n);
    if (dis[t + m * n] >= 0x3f3f3f3f)
        cout << -1;
    else
        cout << dis[t + m * n];
    return 0;
}

方法二：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ppi;
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
int head[maxn], dis[maxn], cnt = 0;
int a[maxn], b[maxn];
struct node
{
   
   int to, w, next;
} e[maxn];

void add(int u, int v, int w)
{
   
   e[++cnt].to = v;
   e[cnt].w = w;
   e[cnt].next = head[u];
   head[u] = cnt;
}

priority_queue<ppi, vector<ppi>, greater<ppi> > q;

void dijkstra(int s)
{
   
   memset(dis, inf, sizeof(dis));
   dis[s] = 0;
   q.push(ppi(0, s));
   while (!q.empty())
   {
   
      int a = q.top().first;
      int b = q.top().second;
      q.pop();
      if (a > dis[b])
         continue;
      for (int i = head[b]; ~i; i = e[i].next)
      {
   
         int v = e[i].to;
         if (dis[v] > dis[b] + e[i].w)
         {
   
            dis[v] = dis[b] + e[i].w;
            q.push(ppi(dis[v], v));
         }
      }
   }
}
int main()
{
   
   int n, m, s, t, sum, x, last;
   scanf("%d%d%d%d", &n, &m, &s, &t);
   memset(head, -1, sizeof(head));
   for (int i = 1; i <= m; ++i)
   {
   
      scanf("%d%d%d", &a[i], &b[i], &sum);
      for (int j = 1; j <= sum; ++j)
      {
   
         scanf("%d", &x);
         if (j != 1)
         {
   
            add(i * n + x, i * n + last, b[i]);
            add(i * n + last, i * n + x, b[i]);
         }
         add(i * n + x, x, 0);
         add(x, i * n + x, a[i]);
         last = x;
      }
   }
   dijkstra(s);
   if (dis[t] != inf)
      printf("%d\n", dis[t]);
   else
      printf("-1\n");
}