时间限制: 1000 ms 内存限制: 65536 KB
提交数: 5585 通过数: 4006
【题目描述】
下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A->E。试用动态规划的最优化原理求出A->E的最省费用。

如图：求v1到v10的最短路径长度及最短路径。

【输入】
第一行为城市的数量N;

后面是N*N的表示两个城市间费用组成的矩阵。

【输出】
A->E的最省费用。

【输入样例】
10
0 2 5 1 0 0 0 0 0 0
0 0 0 0 12 14 0 0 0 0
0 0 0 0 6 10 4 0 0 0
0 0 0 0 13 12 11 0 0 0
0 0 0 0 0 0 0 3 9 0
0 0 0 0 0 0 0 6 5 0
0 0 0 0 0 0 0 0 10 0
0 0 0 0 0 0 0 0 0 5
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0
【输出样例】
minlong=19
1 3 5 8 10

#include <iostream>
#include <cstring>
#include <deque>
#include <stack>
#define N 128
using namespace std;

int GN,dis[N],pos[N];
int n;

bool ved[N];

inline void init()
{
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            cin>>Gi;
            if(Gi==0)
                Gi=0x3f3f3f3f;
        }
    memset(dis,0x3f,sizeof(dis));
}

inline void Spfa()
{
    deque <int> Q;
    Q.push_front(1);
    ved[1]=true;
    dis[1]=0;
    while(!Q.empty())
    {
        int k=Q.front();
        Q.pop_front();
        ved[k]=false;
        
        
        for(int i=1;i<=n;i++)
            if(dis[i]>dis[k]+Gk)
            {
                dis[i]=dis[k]+Gk;
                pos[i]=k;
                if(!ved[i])
                {
                    if(!Q.empty() && dis[i]<dis[Q.front()])
                        Q.push_front(i);
                    else
                        Q.push_back(i);
                    ved[i]=true;
                }
            }
    }
}

stack <int> path;

int calc(int k)
{
    path.push(k);
    if(pos[k]!=0)
        calc(pos[k]);
    else
    {
        while(!path.empty())
        {
            cout<<path.top()<<' ';
            path.pop();
        }
    }
}

int main()
{
    init();
    Spfa();
    cout<<"minlong="<<dis[n]<<endl;
    calc(n);
}