8.城市交通
有n个城市，编号1~n，有些城市之间有路相连，有些则没有，有路则会有一个距离。如图所示是一个含有11个城市的交通图，连线上的数表示距离。现在规定只能从编号小的城市到编号大的城市。问：从编号为1的城市到编号为n的城市的最短距离是多少？
输入：
第一行为n，表示城市数，n<=100。
下面n行是一个n*n的邻接矩阵map[i，j]，其中map[i，j]=0表示城市i和j之间没有路相连，否则为两者之间的距离。
输出：
输出一个数，表示最短距离，保证有解。
输入示例：
11 0 5 3 0 0 0 0 0 0 0 0 5 0 0 1 6 3 0 0 0 0 0 3 0 0 0 8 0 4 0 0 0 0 0 1 0 0 0 0 0 5 6 0 0 0 6 8 0 0 0 0 5 0 0 0 0 3 0 0 0 0 0 0 0 8 0 0 0 4 0 0 0 0 0 0 3 0 0 0 0 5 5 0 0 0 0 0 3 0 0 0 6 0 0 0 0 0 0 4 0 0 0 0 0 8 3 0 0 0 3 0 0 0 0 0 0 0 3 4 3 0 输出示例： 13
解题思路：
1.首先，第一个解决的问题便是如何从矩阵中获取到两个城市之间的距离，如果从i到j可以通路的话，那么map【i】【j】是不为0的，题目中所说只能从编号小的城市到编号大的城市走
2.分析，该用什么方法求解呢？如果到到达城市11，那么只能从8,9,10这三座城市到达，那么只要直到了到达这三座城市的最短路线，然后加上到11的路线，选取三个和中的最小值那么便是最优解，如何求解到达8,9,10这三座城市的最短路线呢？又回到了这个问题，那么看看哪些城市能到达这三座城市，然后同样的方法，保存最优解即可
3.这样分析，满足了最优解包含最优子结构，并且无后效性（无后效性具体指：现在做的事不会影响过去，并且未来做的事不会影响到现在），我们只需要求得到达每一座城市的最短距离，然后求解下一阶段即可
4.设置状态：dp【i】表示从城市1到城市i的最短距离
5.状态转移：从比i号城市小的城市编号中依次遍历，如果这两个城市有路的话，那么就在dp[i]和dp[j]+map[i][j]中选择最小值，即dp[i]=min(dp[i],dp[j]+map[i,j]);
说明：为什么是在dp[i]和dp[j]+a[i][j]中选最小值，拿城市11距离，可以到达的城市为8,9,10，首先肯定先判断城市8+a[11][8]，因为dp[11]是一个很大的数，选择最小值必然会被取代，那么接下来判断城市9-11，此时的dp[11]已经更新，所以是在拿8-11的距离和9-11的距离在选最小值！
6.初始状态：既然要选择最小值的话，那么dp中的最短路初始化为一个很大的数，dp[1]=0，表示从城市1到城市1的距离为0；
7.求目标值dp[n]
#include<bits/stdc++.h>
using namespace std;
int a[105][105],dp[105];
const int MAX=999999999;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cin>>a[i][j];
}//输入数据
for(int i=2;i<=n;i++)
dp[i]=MAX;//设置初始状态
for(int i=2;i<=n;i++)//递推求解到达每一个城市的最短路
{
for(int j=1;j<i;j++)//枚举可以到达i城市的城市
{
if(a[i][j]!=0)//如果这两个城市有路
dp[i]=min(dp[i],dp[j]+a[i][j]);//选取最小值更新
}
}
cout<<dp[n];//输出目标值
return 0;
}