最短路中的路径还原问题

问题描述：
求出源点1到顶点3的最短路长度并依次输出该路径上的顶点
代码：

struct edge
{
    int to;
    int next;
    int w;
};
edge e[500010];
int head[10010];
int cnt = 1;

int n,m;
bool book[10010];
int dis[10010],prev[10010];//prev记录前驱
void add_edge(int u,int v,int w)
{
    e[cnt].to = v;
    e[cnt].next = head[u];
    e[cnt].w = w;
    head[u] = cnt;
    cnt++;
}
void dijkstra(int s)
{
    memset(dis,0x3F,sizeof(dis));//初始化
    memset(prev,-1,sizeof(prev));//初始化
    dis[s] = 0;
// for(int i = head[s]; i != -1; i = e[i].next)
// {
// int to = e[i].to;
// int w = e[i].w;
// dis[to] = min(dis[to],w);//在此处进行判断
// }
// book[s] = true;
    int p;
    for(int i = 1; i <= n - 1; ++i)
    {
        int min_w = inf;
// s可以到达p不等于s与p之间有边相连
// for(int j = head[s]; j != -1; j = e[j].next)
// {
// int to = e[j].to;
// int w = e[j].w;
// if(book[to] == false && dis[to] < min_w)
// {
// min_w = dis[to];
// p = to;
// }
// }
        for(int j = 1; j <= n; ++j)
        {
            if(book[j] == false && dis[j] < min_w)
            {
                min_w = dis[j];
                p = j;
            }
        }
        book[p] = true;
        for(int j = head[p]; j != -1; j = e[j].next)
        {
            int to = e[j].to;
            int w = e[j].w;
            if(dis[to] > dis[p] + w && book[to] == false)
            {
                dis[to] = dis[p] + w;
                prev[to] = p;//中转点p成为了顶点to的前驱顶点
            }
        }
    }
    return;
}
vector<int> get_path(int n)
{
    vector<int> v;
    for(int i = n; i != -1; i = prev[i])//从顶点n开始，向前回溯，直到到达源点
        v.push_back(i);
    reverse(v.begin(),v.end());//翻转
    return v;
}
int main()
{
    cin >> n >> m;
    memset(head,-1,sizeof(head));//初始化
    for(int i = 1; i <= m; ++i)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add_edge(u,v,w);
    }
    dijkstra(1);
    for(int i = 1; i <= n; i++)//输出
    {
        if(dis[i] == inf)
            printf("2147483647 ");
        else
            printf("%d ",dis[i]);
    }
    cout << endl;
    vector<int> path = get_path(3);//还原1->3的路径
    for(int i = 0; i <= path.size() - 1; ++i)//输出路径
        printf("%d ",path[i]);
    cout << endl;
    return 0;
}

解决方法：
代码部分有两处被注释，第一处是对dis数组的初始化，这完全是多此一举，而且由于重边的存在，不写取min会WA，还增长了代码长度。直接将源点进行标记，用源点去松弛源点到其余各点的距离就行，不会产生什么负面影响。如果要写这部分的话，还应在代码中加入求prev的语句。
第二处是在求到源点的最短距离的顶点时，错误地仅在与源点直接有边的顶点中去找，对代码思想不够掌握，造成了错误。
当更新prev[to] = p;时，prev[p]已被求出。