出现了重边怎么破????

#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#define inf 1000000
int v[101][101],loop[101][101];
using namespace std;
int main(){
int n,m;
while(scanf("%d %d",&n,&m)!=EOF){
int a,b,c;
int ans=inf;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(i==j) v[i][j]=loop[i][j]=0;
else v[i][j]=loop[i][j]=inf;
}
for(int i=1;i<=m;i++){
scanf("%d %d %d",&a,&b,&c);
// if(c<v[a][b])
v[b][a]=loop[a][b]=v[a][b]=loop[b][a]=c; <---就是这里,如果注释掉了就过了,可不应该是取最小值吗
}//去重边
for(int k=1;k<=n;k++){
//最小环问题,枚举的点放在最外层循环,且先对环用K进行更新,再更新边,避免环用K走了两次, 且v更新,loop为原来的输入值
//o,另外枚举的i>j都必须比k小
for(int i=1;i<k;i++)
for(int j=1;j<i;j++){
ans=min(ans,v[i][j]+loop[i][k]+loop[k][j]);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
v[i][j]=min(v[i][j],v[i][k]+v[k][j]);
}
if(ans==inf) printf("No solution.\n") ;
else printf("%d\n",ans);
}
return 0;
}

2 条评论

  • @ 2017-03-17 07:47:55

    链式前向星大法好

  • @ 2017-03-16 16:14:08

    取了最小值也要更新啊
    应该是
    if(c<v[a][b])
    v[b][a]=loop[a][b]=v[a][b]=loop[b][a]=c;
    else
    v[a][b]=loop[a][b]=c;

  • 1

信息

ID
1046
难度
6
分类
图结构 | 最短路 点击显示
标签
(无)
递交数
4756
已通过
1265
通过率
27%
被复制
10
上传者