评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 636 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 640 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 640 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 636 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 644 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 636 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 640 KiB, score = 10
测试数据 #7: Accepted, time = 46 ms, mem = 636 KiB, score = 10
测试数据 #8: Accepted, time = 125 ms, mem = 640 KiB, score = 10
测试数据 #9: Accepted, time = 218 ms, mem = 640 KiB, score = 10
Accepted, time = 465 ms, mem = 644 KiB, score = 100

No solution后要加点。。。WA90交了十遍。
傻比题目毁我青春。

典型的Floyd求最小环。

当然我们在这里可以选用dijkstra算法，但是其时间复杂度过高，而且代码的长度与复杂度也绝对没有Floyd简单，所以用Floyd即可。

C++ code

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <algorithm>
#include <iostream>
#include <ctype.h>
#include <set>
#define maxn 1000000
using namespace std;

int g[120][120],dis[120][120],i,j,q,n,num,u,v,m,w,ans;

int minc(void){
int i,j,k,re;
re=maxn;
for(k=1;k<=n;k++){
for(i=1;i<k;i++)
for(j=1;j<i;j++)
re=min(re,dis[i][j]+g[j][k]+g[k][i]);
for(i=1;i<=n;i++)
for(j=1;j<i;j++)
dis[i][j]=dis[j][i]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
return re;
}

int main(){
while(scanf("%d%d",&n,&m)!=EOF){
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
dis[i][j]=g[i][j]=maxn;
for(i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
dis[u][v]=dis[v][u]=g[u][v]=g[v][u]=w;
}
ans=minc();
if(ans==maxn){printf("No solution.\n");}
else{printf("%d\n",ans);}
}
return 0;
}

数据什么鬼，用0x3f初始化数组WA，用0x2f还是WA，后来看下面的题解，用1000000终于过了，日了狗的
c++
#include <cstdio>
int m,n,a[101][101],f[101][101],ans;
int u,v,w;
int fmin(int a,int b){
return a<b?a:b;
}
int main(){
while (scanf("%d%d",&n,&m)!=EOF && n && m){
ans=1000000;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++) f[i][j]=a[i][j]=1000000;
for (int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
a[u][v]=a[v][u]=f[u][v]=f[v][u]=w;
}
for (int k=1;k<=n;k++){
for (int i=1;i<=k-1;i++)
for (int j=i+1;j<=k-1;j++)
ans=fmin(ans,f[i][j]+a[i][k]+a[k][j]);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
f[i][j]=fmin(f[i][j],f[i][k]+f[k][j]);
}
if (ans<1000000) printf("%d\n",ans);
else puts("No solution.\n");
}
}


11

题解与程序

一定要readln啊！！！！！！！！！！！！！！！！！！！坑死我了

输出最好用cout,否则可能出现编译器问题
以及f,g两个数组的赋值要注意，赋的值小了，之后no solution会判断错误，赋值大了，容易出现bug....
被卡了超久.....

以及这一题最小环没有什么好说的了

最小环我擦。。。
但好歹终于AC了啊。。。。

算法解析&&AC代码 欢迎讨论http://blog.csdn.net/loriex/article/details/19284161

详见http://user.qzone.qq.com/969519450/2
#include<stdio.h>
using namespace std;
long long f[101][101],map[101][101],ans,oo=99999999;
long i,j,k,n,m,x,y,z;
int main()
{
while (scanf("%ld%ld",&n,&m)!=EOF)
{
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{
f[i][j]=oo;
map[i][j]=oo;
}
for (i=1;i<=m;i++)
{
scanf("%ld%ld%ld",&x,&y,&z);
map[x][y]=z;map[y][x]=z;
f[x][y]=z;f[y][x]=z;
}
ans=oo;
for (k=1;k<=n;k++)
{
for (i=1;i<=k-1;i++)

for (j=i+1;j<=k-1;j++)
if (f[i][j]+map[i][k]+map[k][j]<ans)
ans=f[i][j]+map[i][k]+map[k][j];
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if ((f[i][k]+f[k][j]<f[i][j])) f[i][j]=f[i][k]+f[k][j];
}
if (ans<oo) printf("%ld\n",ans);
else printf("No solution.\n");
}
}

AC123

floyd最小环。。
数据太坑了。。。赋极大值也会加爆。。。O(∩_∩)O~幸亏我有测试数据
Pascal代码如下：
Var f,a:array[1..100,1..100] of longint;
u,v,w,i,j,k,m,n,ans:longint;
Function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
End;
Procedure init;
Var i,j:longint;
Begin
ans:=1000000;
Readln(n,m);
For i:=1 to n do
For j:=1 to n do
Begin
f[i,j]:=1000000;
a[i,j]:=1000000;
End;
For i:=1 to m do
Begin
Readln(u,v,w);
a[u,v]:=w;
f[u,v]:=w;
a[v,u]:=w;
f[v,u]:=w;
End;
End;
Procedure main;
Var i,j,k:longint;
Begin
For k:=1 to n do
Begin
For i:=1 to k-1 do
For j:=i+1 to k-1 do
ans:=min(ans,f[i,j]+a[i,k]+a[k,j]);
For i:=1 to n do
For j:=1 to n do
f[i,j]:=min(f[i,j],f[i,k]+f[k,j]);
End;
End;
Begin
While not eof do
Begin
init;
main;
If ans<1000000 then Writeln(ans) else writeln('No solution.');
End;
End.

#include<stdio.h>
#include <iostream>
using namespace std;

const long MAX=1000000;
long n,m,x,y,d;
long dist[111][111],map[111][111],ans;
long min(long a,long b)
{
if(a<b) return a;
else return b;
}
int main()
{
while(scanf("%ld%ld",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
map[i][j]=MAX;
for(int i=1;i<=m;i++)
{
cin>>x>>y>>d;
map[x][y]=d;
map[y][x]=d;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dist[i][j]=map[i][j];
ans=MAX;
for(int k=1;k<=n;k++)
{
for(int i=1;i<k;i++)
for(int j=i+1;j<k;j++)
ans=min(dist[i][j]+map[i][k]+map[k][j],ans);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dist[i][j]=min(dist[i][k]+dist[k][j],dist[i][j]);
}
if(ans==MAX)
cout<<"No solution."<<endl;
else cout<<ans<<endl;
}
return 0;
}

#include <iostream>
using namespace std;
#define IN 100000000
int main()
{

int i,j,k,x1,x2,n,m;
long ans,l;
long g[100][100];
long dist[100][100];

while(cin>>n>>m)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
g[i][j]=IN;

for(i=0;i<m;i++)
{
cin>>x1>>x2>>l;
g[x1-1][x2-1]=l;
g[x2-1][x1-1]=l;
}
for(i=0;i<n;i++)
g[i][i]=0;

for(i=0;i<n;i++)
for(j=0;j<n;j++)
dist[i][j]=g[i][j];

ans=IN;
for(k=0;k<n;k++)
{

for(i=0;i<k;i++)
for(j=0;j<i;j++)
if(dist[i][j]+g[i][k]+g[k][j]<ans)
ans=dist[i][j]+g[i][k]+g[k][j];

for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(dist[i][k]+dist[k][j]<dist[i][j])
dist[i][j]=dist[i][k]+dist[k][j];
}

if(ans!=IN)
cout<<ans<<endl;
else
cout<<"No solution."<<endl;

}
return 0;

}

floyd求最小环
为什么总是只有70分，第一个点就WA了
#include <iostream>
using namespace std;
int main()
{

int i,j,k,x1,x2,n,m;
long ans,l;
long g[100][100];
long dist[100][100];

while(cin>>n>>m)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
g[i][j]=10000000;

for(i=0;i<m;i++)
{
cin>>x1>>x2>>l;
g[x1-1][x2-1]=l;
g[x2-1][x1-1]=l;
}

for(i=0;i<n;i++)
for(j=0;j<n;j++)
dist[i][j]=g[i][j];

ans=10000000;
for(k=0;k<n;k++)
{

for(i=0;i<k-1;i++)
for(j=i+1;j<k-1;j++)
if(dist[i][j]+g[i][k]+g[k][j]<ans)
ans=dist[i][j]+g[i][k]+g[k][j];

for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(dist[i][k]+dist[k][j]<dist[i][j])
dist[i][j]=dist[i][k]+dist[k][j];
}

if(ans!=10000000)
cout<<ans<<endl;
else
cout<<"No solution."<<endl;

}
return 0;

}

点击查看程序源码+详细题解

哥无语了 、 我想了很久以为要经过所有景点、

#include

#include

#define MAXN 100

#define INF 10000000

#define MIN(a,b)((a) > (b) ? (b) : (a))

using namespace std;

int N , M ;

int r[MAXN][MAXN] , f[MAXN][MAXN];

void Solve()

{

for (int i = 1 ; i

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 369ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 338ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 244ms

├ 测试数据 10：答案正确... 619ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1570ms

人FLOYD我FLOYD怎么我这么猥琐……

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 103ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 181ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 72ms

├ 测试数据 10：答案正确... 181ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：537ms

虽然有点慢，还是要感谢楼下厦门一中大牛啊。

在此提醒各位注意：

1：用eof

2：用readln;

利用此题练了一下dijkstra,不错！

var

n,m,i,j,k,best:longint;

b,c:array[0..10001]of longint;

a:array[0..101,0..101]of longint;

v,min:longint;

p:array[0..101]of boolean;

dis:array[0..101]of longint;

procedure dijkstra(v0,v1:longint);

var

i,j:longint;

begin

fillchar(p,sizeof(p),true);

v:=v0;

p[v]:=false;

for i:=1 to n do

if a[v,i]0 then

dis[i]:=a[v,i]

else

dis[i]:=maxlongint;

while vv1 do

begin

min:=maxlongint;

j:=0;

for i:=1 to n do

if (p[i]) and (dis[i]

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

floyd求最小环。