请设计一道有题目背景考察最短路算法的编程问题不少于500字

题目背景：

某市规划了一条新的地铁线路，连接了市区的两个重要商业区域。为了方便市民出行，需要设计一个最短路算法来确定地铁线路的最短路径。

问题描述：

假设该市的地铁系统是一个有向图，图中每个节点代表一个地铁站，每条边代表两个地铁站之间的连接，边上的权值表示两个地铁站之间的距离。为了方便起见，我们假设该图是一个有向无环图（DAG）。

请设计一个最短路算法，计算从起点到终点的最短路径，并输出路径上每个节点的编号和对应的距离。

输入格式：

输入的第一行包含四个整数N、M、S和T，其中N表示地铁站的数量，M表示有向边的数量，S表示起点的编号，T表示终点的编号。

接下来M行，每行包含三个整数x、y和z，表示从地铁站x到地铁站y有一条有向边，边的权值为z。

输出格式：

输出一行，包含两个整数，分别表示从起点到终点的最短路径长度和路径上经过的节点编号。

例如，如果输入如下：

5 7 1 5 1 2 2 1 3 5 2 4 3 2 5 1 3 4 1 4 5 1 1 5 7

输出如下：

6 1 2 4 5

解题思路：

这道题的核心是求解从起点到终点的最短路径。我们可以使用Dijkstra算法或Bellman-Ford算法来解决该问题。

Dijkstra算法的时间复杂度为O(N^2)，适用于稠密图；Bellman-Ford算法的时间复杂度为O(NM)，适用于稀疏图。根据该图是DAG的特点，我们可以使用拓扑排序和动态规划的思想来设计算法，时间复杂度为O(N+M)。

具体实现：

对该图进行拓扑排序，得到每个节点的拓扑序列，即每个节点的入度为0的序列。
初始化最短路径数组dist和路径数组path，dist[i]表示起点到节点i的最短路径长度，path[i]表示起点到节点i的最短路径上节点i的前驱节点。
对于拓扑序列中的每个节点i，遍历该节点的所有出边，更新该节点的后继节点的最短路径长度和路径数组。具体操作如下：

对于每个后继节点j，如果dist[j]>dist[i]+w(i,j)，则更新dist[j]为dist[i]+w(i,j)，更新path[j]为i。

循环结束后，path数组存储了从起点到终点的最短路径上每个节点的前驱节点，我们可以根据path数组逆向输出最短路径上的节点编号。

时间复杂度为O(N+M)，空间复杂度为O(N)。

代码实现：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

const int N=100010,M=200010;

int n,m,s,t;
int h[N],e[M],ne[M],w[M],idx;
int dist[N],path[N],cnt[N];
int q[N];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

bool topsort()
{
    int tt=-1,hh=0;
    for(int i=1;i<=n;i++) 
        if(!cnt[i]) q[++tt]=i;

    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(--cnt[j]==0) q[++tt]=j;
        }
    }

    return tt==n-1;
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m>>s>>t;
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        cnt[b]++;
    }

    if(!topsort()) cout<<"-1"<<endl;
    else
    {
        memset(dist,0x3f,sizeof dist);
        dist[s]=0;
        for(int i=0;i<n;i++)
        {
            int t=q[i];
            for(int j=h[t];~j;j=ne[j])
            {
                int k=e[j];
                if(dist[k]>dist[t]+w[j])
                {
                    dist[k]=dist[t]+w[j];
                    path[k]=t;
                }
            }
        }

        vector<int> res;
        for(int i=t;i!=s;i=path[i]) res.push_back(i);
        res.push_back(s);
        reverse(res.begin(),res.end());
        cout<<dist[t]<<" ";
        for(auto i:res) cout<<i<<" ";
        cout<<endl;
    }

    return 0;
}
``