题解 P1828 【香甜的黄油 Sweet Butter】
shadowice1984
2017-09-25 13:36:59
floyd优化~~~
楼下大佬说floyd会超时，果真如此；
然而勒，路径都是双向边！
所以从i到j的距离等于j到i的距离~；
然后，就砍了一半的枝。
就过了········
************************************
方便萌新，写一下floyd的原理。
从i到j有两种途径，直接从i到j（路径不存在耗时即为无穷）
或者从i到k再从k到i。
然后选较短的就行了。
ps：邻接矩阵存图。
上代码~
```cpp
#include<stdio.h>
using namespace std;
int n;int p;int c;
int map[800][805];
int d[805][805];
int mark[805];
const int inf=9999999;
int res=inf;
int main()
{
scanf("%d%d%d",&n,&p,&c);
for(int i=0;i<p;i++)//手动memset
{
for(int j=0;j<p;j++)
{
if(i==j)
{
map[i][j]=0;//到自己的距离为0
d[i][j]=0;
}
else
{
map[i][j]=inf;
d[i][j]=inf;
}
}
}
for(int i=0;i<n;i++)
{
int t;
scanf("%d",&t);
mark[t-1]++;//从零开始的数组
}
for(int i=0;i<c;i++)
{
int u;int v;int val;
scanf("%d%d%d",&u,&v,&val);
map[u-1][v-1]=val;//从零开始的数组
map[v-1][u-1]=val;
d[u-1][v-1]=val;//初始化d为邻接矩阵
d[v-1][u-1]=val;
}
for(int k=0;k<p;k++)//floyd三重循环
{
for(int i=0;i<p;i++)
{
for(int j=0;j<i;j++)//灵魂剪枝，双向边算一半图就好了
{
if(d[i][j]>d[i][k]+d[k][j])
{
d[i][j]=d[i][k]+d[k][j];
d[j][i]=d[i][j];//更新另一半
}
}
}
}
for(int i=0;i<p;i++)//扫一遍，寻找最短路径和
{
int sum=0;
for(int j=0;j<p;j++)
{
sum+=d[i][j]*mark[j];//因为是路径和，所以用mark数组保存奶牛头数
}
if(res>sum)res=sum;
}
printf("%d",res);
return 0;//拜拜程序~
}
```