这个格式？？什么鬼
by Jigsaw_Killer @ 2018-07-28 16:37:36
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
int N,M,num[105][105],op[105][105],ans=0,ans1=0,du[5005][2],num1[105][105],ans2=0;
using namespace std;
void read()
{
memset(num,0x3f,sizeof(num));
scanf("%d%d",&N,&M);
for(int a=0;a<M;a++)
{
int b,c;
scanf("%d%d",&du[a][0],&du[a][1]);
scanf("%d",&num[du[a][0]-1][du[a][1]-1]);
//printf("\n");
num[du[a][1]-1][du[a][0]-1]=num[du[a][0]-1][du[a][1]-1];
//printf("%d %d %d %d\n",du[a][0],du[a][1],num[du[a][0]-1][du[a][1]-1],num[du[a][1]-1][du[a][0]-1]);
}
//for(int a=0;a<N;a++)
//num[a][a]=0;
for(int a=0;a<N;a++)
{
}
return;
}
int ge(int i,int j)
{
if(i==j)
return 0;
if(op[i][j]==0)
return num1[i][j];
ans=max(ans,max(ge(i,op[i][j]),ge(op[i][j],j)));
//printf("%d\n",max(ge(i,op[i][j]),ge(op[i][j],j)));
}
int main ()
{
read();
for(int a=0;a<N;a++)
for(int b=0;b<N;b++)
num1[a][b]=num[a][b];
for(int k=0;k<N;k++)
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
if(num1[i][j]>num1[i][k]+num1[k][j])
num1[i][j]=num1[i][k]+num1[k][j],op[i][j]=k;
int kkk=num1[0][N-1];
ge(0,N-1);
for(int a=0;a<M;a++)
{
if(num[du[a][0]-1][du[a][1]-1]==ans)
{
for(int a=0;a<N;a++)
for(int b=0;b<N;b++)
num1[a][b]=num[a][b];
num1[du[a][0]-1][du[a][1]-1]=ans*2;
num1[du[a][1]-1][du[a][0]-1]=ans*2;
for(int k=0;k<N;k++)
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
if(num1[i][j]>num1[i][k]+num1[k][j])
num1[i][j]=num1[i][k]+num1[k][j];
ans2=max(ans2,num1[0][N-1]-kkk);
}
}
printf("%d",ans2);
return 0;
}
```
by Jigsaw_Killer @ 2018-07-28 16:38:37
好了好了
by Jigsaw_Killer @ 2018-07-28 16:38:56
这是Floyd，本蒟蒻水平有限，最后只能暴力...结果没有超时，但是WA了两个点。我觉得是数据太水，不然我应该30分都没有
by Jigsaw_Killer @ 2018-07-28 16:41:58
WA了2,8两个点
by Jigsaw_Killer @ 2018-07-28 16:46:16
@[AC400](/space/show?uid=55690) 我怎么觉得是ijk+一个m的枚举呢。。。
by 斗神·君莫笑 @ 2018-07-28 16:49:38
@[AC400](/space/show?uid=55690) 哦不不不，一定在最短路上，因此只用在最短路上枚举，但万一毒瘤数据还是nlognm
by 斗神·君莫笑 @ 2018-07-28 16:50:40
@[斗神·君莫笑](/space/show?uid=49644) ？？？dalao我听不懂什么意思
by Jigsaw_Killer @ 2018-07-28 16:51:10
@[AC400](/space/show?uid=55690) 就是先用ijk跑最短路，然后一个个枚举~~（刚敲完板子的蒟蒻想法）~~
by 斗神·君莫笑 @ 2018-07-28 16:52:04
@[AC400](/space/show?uid=55690) 看来题解也是这么想的（数据范围水了）
by 斗神·君莫笑 @ 2018-07-28 16:54:52