HDU 1599 find the mincost route(Floyd无向图最小环)
find the mincost route
杭州有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)。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 1Sample Output
3 It's impossible.
从1开始~请问最短路线回到1的长度是多少~~这道题的实质就是让你求最小环（至少3点）的长度~~
我们可以用floyd的方法来做~~
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
#define inf 10000000
int n, m, a, b, c;//注意这里不能用0x3f3f3f3f!!因为可能连续3个inf相加~~超出int范围
int map[105][105];//来储存边的长度；
int A[105][105];//a到b的最短边；
int floyd()
{
int minn = inf;
for (int s = 1; s <= n; s++)
{
for (int e = 1; e < s; e++)
{
for (int w = e + 1; w < s; w++)
{
int t = A[e][w] + map[e][s] + map[s][w];//点至少为3的环~~至于为什么用map~是因为用最小A的情况下可能会重复路径
if (t < minn)
{
minn = t;
}
}
}
for (int e = 1; e <= n; e++)
{
for (int w = 1; w <= n; w++)
{
if (A[e][w] > A[e][s] + A[s][w])
{
A[e][w] = A[e][s] + A[s][w];//更新~
}
}
}
}
return minn;
}
int main()
{
while (cin >> n >> m)
{
for (int s = 1; s <= n; s++)
{
for (int e = 1; e <= n; e++)
{
map[s][e] = A[s][e] = inf;//初始化
}
}
for (int s = 1; s <= m; s++)
{
cin >> a >> b >> c;
map[a][b] = map[b][a] = A[a][b] = A[b][a] = min(map[a][b], c);//建图
}
int ans = floyd();
if (ans == inf)
{
cout << "It's impossible.\n";
}
else
{
cout << ans << endl;
}
}
return 0;
}
投递美团等公司9个岗位
美的集团公司氛围 364人发布