本文共 1499 字，大约阅读时间需要 4 分钟。

Description

在桑给巴尔岛的Adelton城镇上有一个旅游机构。它们决定在提供许多的其它吸引之外，再向客人们提供旅游本镇的服务。 为了从提供的吸引服务中尽可能地获利，这个旅游机构接收了一个精明决定：在相同的起点与终点之间找出一最短路线。

Input

你的任务是编写一条程序来找类似的的一条路线。在这个镇上，有N个十字路口(编号1至N)，两个十字路口之间可以有多条道路连接，有M条道路（编号为1至M)。但没有一条道路从一个十字路口出发又回到同一个路口。每一条观光路线都是由一些路组成的，这些道路序号是：y1, …, yk,且k>2。第yi(1<=i<=k-1)号路是连接第xi号十字路口和第x［i+1］号十字路口的；其中第yk号路是连接第xk号十字路口和第x[k+1]号十字路口。而且所有的这些x1,…,xk分别代表不同路口的序号。在某一条观光路线上所有道路的长度的和就是这条观光路线的总长度。换言之L(y1)+L(y2)+…+L(yk)的和, L(yi)就是第yi号观光路线的长度。你的程序必须找出类似的一条路线：长度必须最小，或者说明在这个城镇上不存在这条观光路线。

Output

每组数据的第一行包含两个正整数：十字路口的个数N(N<=100)，另一个是道路的 数目M(M<10000)。接下来的每一行描述一条路：每一行有三个正整数：这条路连接的两个路口的编号，以及这条路的长度（小于500的正整数）。

思路

设dis[i][j]为i到j之间的最短路，g[i][j]为链接i、j的边的权值。
然后边Floyed边处理。枚举k，以它为最大节点。枚举i，j小于k，形成一个环，

代码：

#include<cstdio>#include<iostream>#include<cstring>using namespace std;int n,m,a[101][101],d[101][101],ans=100000000;int main(){
       memset(a,127/3,sizeof(a));        //初始化，0x7f会炸？？？    memset(d,127/3,sizeof(d));    scanf("%d%d",&n,&m);    for(int i=1;i<=m;++i){
       	int x,y,z;         scanf("%d%d%d",&x,&y,&z);         a[x][y]=z;a[y][x]=z;        //双向表         d[x][y]=z;d[y][x]=z;    }    for(int k=1;k<=n;k++){
              //Floyed    	for(int i=1;i<k;++i)         //枚举i，j，k构成一个环    	  for(int j=i+1;j<k;++j)            ans=min(ans,d[i][j]+a[i][k]+a[k][j]); //环的大小        for(int i=1;i<=n;++i)       //普通Floyed          for(int j=1;j<=n;++j)            d[i][j]=min(d[i][j],d[i][k]+d[k][j]);    }    if(ans==100000000||ans<0) printf("No solution"); //如果不存在环    else printf("%d",ans);  //输出}