城市交通路网

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<vector<int> > map(1005,vector<int>(1005,0));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>map[i][j];
        }
    }
    int dp[1005];//dp[i]记录i节点到终点E的最短距离 
    int index[1005]={0};
    //初始化
    dp[n]=0;
    for(int i=1;i<n;i++)
    {
        dp[i]=100000;
    }
    for(int i=n-1;i>0;i--)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(map[i][j]!=0&&dp[i]>map[i][j]+dp[j])
            {
                dp[i]=dp[j]+map[i][j];
                index[i]=j;
            }
        }
    } 
    cout<<"minlong="<<dp[1]<<endl;
    int i=1;
    while(i)
    {
        cout<<i<<' ';
        i=index[i];
    }
    return 0;
}