2019年百度之星 - 初赛三B 最短路 2(Floyd+思维)
程序员文章站
2022-06-03 18:31:51
...
题目链接:https://vjudge.net/contest/351693#problem/C
分析:求i—>j的最短路,可能通过别的点进行中间扩展,Di,j就是中间扩展最大的那个点。
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e3+10;
const LL INF=0x3f3f3f3f3f3f3f3f;
const int mod=998244353;
LL e[N][N],a[N][N];
int n,m;
void init()
{
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
if(i==j)
e[i][j]=0;
else
e[i][j]=INF;
}
memset(a,0,sizeof(a));
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
init();
while(m--)
{
int u,v;
LL w;
scanf("%d%d%lld",&u,&v,&w);
e[u][v]=e[v][u]=min(e[u][v],w);
}
LL sum=0;
for(int k=1; k<=n; k++)
{
for(int i=1; i<=n; i++)
{
if(e[i][k]==INF)/*相当于剪枝*/
continue;
for(int j=1; j<i; j++)/*求一遍,再乘以2*/
{
if(e[i][j]>e[i][k]+e[k][j])
{
sum+=(LL)k;
sum-=a[i][j];
a[i][j]=a[j][i]=(LL)k;
e[i][j]=e[j][i]=e[i][k]+e[k][j];
}
}
}
}
sum=sum*2;
sum=sum%mod;
printf("%lld\n",sum);
}
return 0;
}
上一篇: PHP与数据库链接,该怎么处理
下一篇: 数据结构--无向图满足约束条件的通路