深圳宝安区住房和建设局网站官网,校园网站建设方案策划书,济南做网站互联网公司有哪些,上海华讯网络公司排名题干#xff1a;
杭州有N个景区#xff0c;景区之间有一些双向的路来连接#xff0c;现在8600想找一条旅游路线#xff0c;这个路线从A点出发并且最后回到A点#xff0c;假设经过的路线为V1,V2,....VK,V1,那么必须满足K2,就是说至除了出发点以外至少要经过2个其他不同…题干
杭州有N个景区景区之间有一些双向的路来连接现在8600想找一条旅游路线这个路线从A点出发并且最后回到A点假设经过的路线为V1,V2,....VK,V1,那么必须满足K2,就是说至除了出发点以外至少要经过2个其他不同的景区而且不能重复经过同一个景区。现在8600需要你帮他找一条这样的路线并且花费越少越好。
Input
第一行是2个整数N和MN 100, M 1000)代表景区的个数和道路的条数。 接下来的M行里每行包括3个整数a,b,c.代表a和b之间有一条通路并且需要花费c元(c 100)。
Output
对于每个测试实例如果能找到这样一条路线的话输出花费的最小值。如果找不到的话输出Its 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
Its impossible.
解题报告 模板就是了。。注释下面有。不解释了、、其实还有个更朴素的做法用Dijkstra也可以求最小环ps最小生成树是不是也可以
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
ll dis[505][505];//Floyd更新后数据
ll maze[505][505];//原始数据
const ll INF 0x3f3f3f3f3f3f;
int n,m;
ll floyd() {ll res INF;for(int k 1; kn; k) {for(int i 1; ik; i) {for(int j i1; jk; j) {res min(res,maze[i][k] maze[k][j] dis[i][j]);}}for(int i 1; in; i) {for(int j 1; jn; j) {dis[i][j] min(dis[i][j] , dis[i][k] dis[k][j]);}}} return res;
}int main()
{ll w;while(cinnm) {for(int i 1; in; i) {for(int j 1; jn; j) {dis[i][j] maze[i][j] INF;}}for(int i 1,a,b; im; i) {scanf(%d%d%lld,a,b,w);if(w maze[a][b]) maze[a][b] maze[b][a] dis[a][b] dis[b][a] w;}ll ans floyd();if(ans INF) puts(Its impossible.);else printf(%lld\n,ans);}return 0 ;}
贴一个代码的讲解
#includecstdio
#includealgorithm
#includecstring
using namespace std;
const int INF0xfffffff;
//const int INF0x3f3f3f3f; 这里用这个就 WA 想不通为啥
//当然WA了。。因为三个INF相加就溢出了啊
int n,m;
int map[110][110],dist[110][110];
void floyd() {int ansINF;for(int k1; kn; k) {for(int i1; ik; i) { // 一个环至少要 3个互不相同点所以保证 k大于 ii大于 jfor(int ji1; jk; j) {ansmin(ans,map[i][k]map[k][j]dist[i][j]); // 得到从 i点出发再回到 i点的最小环}}for(int i1; in; i) {for(int j1; jn; j) {dist[i][j]min(dist[i][j],dist[i][k]dist[k][j]); // 得到 ij两点的最短路径}}//注意求最短路径的循环一定要放在求最小环的循环的下面这是为了保证 dist[i][j]与 map[i][k]map[k][j]不会重路// ans min ( ans , map[i][k] map[k][j] dist[i][j] ) 求最小环式子要求的就是 dist[i][j]中所有的中间点一定小于 k所以不会重路}if(ansINF) puts(Its impossible.);else printf(%d\n,ans);
}
int main() {while(~scanf(%d %d,n,m)) {for(int i1; in; i) {for(int j1; jn; j) {dist[i][j]map[i][j](ij?0:INF);}}int a,b,c;while(m--) {scanf(%d %d %d,a,b,c);if(map[a][b]c) {dist[a][b]dist[b][a]map[a][b]map[b][a]c;}}floyd();}return 0;
}总结 注意这个无向图中你的距离的初始化 到自身可以初始化成0也可以初始化成INF都可以 看心情就行。。 对于有向图就比较简单了可以直接遍历dis[i][i]记录最小值就可以了。
