解析：

这道最短路径的问题，我们还是采用拓扑的思路，反着存图，往回加，走最短的，如果从边上绕路比直接过去省距离，那么就从边上绕路。
还有值得一提的是链式前向星的记录路径：
if(e[i].w + dp[now] < dp[u]){ dp[u] = e[i].w + dp[now]; path[u] = now; }
输出如下：
for(int i = 1;path[i];i=path[i])printf("%d " ,path[i]);
前一个点记录的是自己的前一个端点

完整代码如下：

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

struct Edge{
    int to,nxt,w;
}e[1000001];

int head[100001];
int ecnt = -1;
int n;
int ru[100001];

void addEdge(int x,int y,int w){
    e[++ecnt] = (Edge){y,head[x],w};
    head[x] = ecnt;
}

queue <int> q;
int dp[100001];
int path[1000001];
int id = 1;

void topo_sort(){
    for(int i = 1;i <= n; i++){
	    if(ru[i] == 0) q.push(i);
	    dp[i] = 1e9;
    }
    dp[n] = 0;
    while(!q.empty()){
	    int now = q.front();q.pop();
	    for(int i = head[now]; ~i; i = e[i].nxt){
		    int u = e[i].to;
		    if(e[i].w + dp[now] < dp[u]){
			    dp[u] = e[i].w + dp[now];
			    path[u] = now;
		    }
		    if(!--ru[u]){
			    q.push(u);
		    }
	    }
    }
}

int main()
{
    scanf("%d" ,&n);
    memset(head,-1,sizeof(head));
    for(int i = 1;i <= n; i++){
	    for(int j = 1;j <= n; j++){
		    int c;
		    scanf("%d" ,&c);
		    if(c != 0){
			    addEdge(j,i,c);
			    ru[i]++;
		    }
	    }
    }
    topo_sort();
    printf("%d\n" ,dp[1]);
    for(int i = 1;path[i];i=path[i])printf("%d " ,path[i]);
    return 0;	
}

样例：

题解：最短路径

原文：https://www.cnblogs.com/Crazyman-W/p/14710739.html