【SSL】城市交通

本文主要是介绍【SSL】城市交通，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

城市交通

---

Description

有n个城市，编号1~n，有些城市之间有路相连，有些则没有，有路则当然有一个距离。现在规定只能从编号小的城市到编号大的城市，问你从编号为1的城市到编号为n的城市之间的最短距离是多少？

Input

先输入一个n，表示城市数，n小于100。
下面的n行是一个n*n的邻接矩阵map[i,j],其中map[i,j]=0表示城市i和城市j之间没有路相连，否则为两者之间的距离。

Output

输出格式：一个数，表示最少要多少时间。
输入数据保证可以从城市1飞到城市n。

Sample Input

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

Sample Output

13

解题思路

使用动态规划，状态转移方程是：
$f[i][j]+=s[j]$
$s[i]=min(s[i][j],s[i])$
我的程序使用的是逆推法，但前提是s[i][j]!=0，也可以用顺推。

#include<stdio.h> 
#include<iostream>
using namespace std;
long long n,s[1000][1000],f[1000];
void input()
{scanf("%d",&n);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&s[i][j]);}}
}
void work()
{f[n]=0;for(int i=n-1;i>0;i--){f[i]=100000;for(int j=i+1;j<=n;j++){if(s[i][j]==0)//判断是否等于零continue;s[i][j]+=f[j];f[i]=min(s[i][j],f[i]);//状态转移方程}}cout<<f[1];//输出
}
int main()
{input();work();return 0;
} 

这篇关于【SSL】城市交通的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---