宝安的医院网站建设,门户网站开发需要多少钱,萧山好的做网站的公司,诸城公司做网站廉价最短路径
题目大意#xff1a;
一个图中#xff0c;在满足最短路的前提下#xff0c;求最小代价
原题#xff1a;
题目描述
图是由一组顶点和一组边组成的。一条边连接两个顶点。例如#xff0c;图1表示了一个有4个顶点V、5条边的图。图中#xff0c;每条边e是有…廉价最短路径
题目大意
一个图中在满足最短路的前提下求最小代价
原题
题目描述
图是由一组顶点和一组边组成的。一条边连接两个顶点。例如图1表示了一个有4个顶点V、5条边的图。图中每条边e是有方向的方向从起点到终点并且每条边都有价值。用整数0,1,…,m-1可以表示一个有m个顶点的图。 一条路径连接了一个点Vi和另一个点Vj其方向与经过的一系列边的方向一致。路径的长度是途经边的条数路径的费用是边价值的总和。对于一个给定的图你的任务是在所有最短路径中找出需要最少费用的连接V0和V1的路径。一个需要最少费用的最短路径称之为廉价最短路径。 让我们重新考虑图1从0到1的最短路径是只含一条边的路径0→1费用是10。当然还有更便宜的路0→2→1和 0→3→1但是它们比第一条路径长(有2条边)。所以0→1是廉价最短路径。 看一下另一个例子图2它有2条最短路径其长度是2路径0→3→1(费用4)比路径0→2→1(费用5)花费少。还用另一条路径0→2→3→1(费用3)虽然便宜但是很长。所以廉价最短路径是0→3→1。
输入
输入文件第一行有两个整数m和n用一个空格隔开其中m是顶点数而n是边数。接下来的n行给出所有的边及其价值每行有3个整数(相邻两个整数间有一个空格)表示起点终点和边的价值。顶点最多有100个编号在0到99之间。边最多有1000条其价值在0到2^15-1之间。
输出
输出文件仅有一行包含一个整数即V0→V1的廉价最短路径的费用。当出现有多个廉价最短路径的情况时它们的费用是一样的。
输入样例
4 5
0 2 2
0 3 2
0 1 10
2 1 2
3 1 2输出样例
10说明
东莞市2013年信息学特长生测试题第四题
解题思路
数据很小直接Floyed就可以了
代码
#includecstdio
#includecstring
#includeiostream
using namespace std;
int n,m,x,y,z,a[105][105],c[105][105];
int main()
{scanf(%d %d,n,m);memset(a,127/3,sizeof(a));memset(c,127/3,sizeof(c));for (int i1;im;i){scanf(%d %d %d,x,y,z);a[x][y]z;c[x][y]1;//预处理}for (int k0;k100;k)for (int i0;i100;i)for (int j0;j100;j)if (c[i][k]c[k][j]c[i][j])//求最短路{c[i][j]c[i][k]c[k][j];a[i][j]a[i][k]a[k][j];}else if (c[i][k]c[k][j]c[i][j]a[i][k]a[k][j]a[i][j]) a[i][j]a[i][k]a[k][j];//求最小代价printf(%d,a[0][1]);
}
