本文主要是介绍find the mincost route，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
find the mincost route
Crawling in process... Crawling failed Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Description
杭州有N个景区，景区之间有一些双向的路来连接，现在8600想找一条旅游路线，这个路线从A点出发并且最后回到A点，假设经过的路线为V1,V2,....VK,V1,那么必须满足K>2,就是说至除了出发点以外至少要经过2个其他不同的景区，而且不能重复经过同一个景区。现在8600需要你帮他找一条这样的路线，并且花费越少越好。
Input
第一行是2个整数N和M（N <= 100, M <= 1000)，代表景区的个数和道路的条数。
接下来的M行里，每行包括3个整数a,b,c.代表a和b之间有一条通路，并且需要花费c元(c <= 100)。
接下来的M行里，每行包括3个整数a,b,c.代表a和b之间有一条通路，并且需要花费c元(c <= 100)。
Output
对于每个测试实例，如果能找到这样一条路线的话，输出花费的最小值。如果找不到的话，输出"It's impossible.".
Sample Input
3 3 1 2 1 2 3 1 1 3 1 3 3 1 2 1 1 2 3 2 3 1
Sample Output
3 It's impossible.
对于i到j的最短路径有两种形式，①经过k，最短路径就是i到k加上k到j的距离；②不过k，最短路径就是i 到j的距离。
求无向图最小环，枚举最大环的连接点，更新环，用dist[i][j]表示i到j的最短路径，当前最小环的权用minn表示，则对于每一个接点k （1到k - 1中间结点的最短路径都已经确定）, 有minn = ( dist[i][j] + maze[j][k] + maze[k][i] , minn )，即环的权 = i到j的最短路径(1 < i,j <= k - 1) + jk边 + ki边。
代码：
#include"cstdio"
#include"cstring"
#include"iostream"
#include"algorithm"using namespace std;#define INF 100000000int n,m;
int maze[105][105];
int dist[105][105];void initial()
{for(int i = 0;i < 105;i++){for(int j = 0;j < 105;j++){maze[i][j] = INF;dist[i][j] = INF;}}
}void Floyd()
{int minn = INF;for(int k = 1;k <= n;k++) //对于每一个k值，1到k - 1中间结点的最短路径都已经确定{for(int i = 1;i < k;i++){for(int j = i + 1;j < k;j++){minn = min(dist[i][j] + maze[j][k] + maze[k][i],minn); //更新环的权值}}for(int i = 1;i <= n;i++){for(int j = 1;j <= n;j++){dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]); //保存i到j之间最短路径}}}if(minn == INF){printf("It's impossible.\n");}else{printf("%d\n",minn);}
}int main()
{while(~scanf("%d%d",&n,&m)){initial();int a,b,c;while(m--){scanf("%d%d%d",&a,&b,&c);if(a != b && maze[a][b] > c){maze[a][b] = c;maze[b][a] = c;dist[a][b] = c;dist[b][a] = c;}}Floyd();}return 0;
}
这篇关于find the mincost route的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
