暑假集训(3)第三弹 -----Til the Cows Come Home(Poj2387)

时间:2023-03-09 15:11:36
暑假集训(3)第三弹 -----Til the Cows Come Home(Poj2387)

题意梗概:据说母牛在产奶的时候,因为奶量太充足,希望有人帮它挤奶,它回家就很快。我们便能喝到鲜美的

牛奶,不过,贫奶季节却大不相同,它会懒洋洋的在大草原上晃来晃去的晒太阳,而不会想到马上回家,这可不

是好兆头,这意味着它没时间睡好觉,随之产奶的质量又会下降。

为了喝到高质量的鲜牛奶,以促进身体发育,长得更高,你希望它能尽快的回家睡觉,所以你要在给定的几条小

路中找到能回家最短的路径组合。

题目分析:还是求最短路径,可以用dijkstra算法解题,这方法我也不是特别懂,照着书上打完,再改了一下,就

过了......

 #include "cstdio"
#define INF 1000100
int v[];
int d[][];
int l[];
int min(int x,int y)
{
return x>y?y:x;
}
void abegin(int n)
{
for (int i=;i<n;i++)
{
v[i] = ;
l[i]= (i == n-?:INF);
for (int j=;j<n;j++)
d[i][j] =INF;
}
}
int main()
{
int t,n;
int a,b,c,x;
while (scanf ("%d%d",&t,&n)!= EOF)
{
abegin(n);
while (t--)
{
scanf ("%d%d%d",&a,&b,&c);
if (c < d[a-][b-])
{
d[a-][b-] = c;
d[b-][a-] = c;
}
}
for (int k=;k<n;k++)
{
c = INF;
for (int i=;i<n;i++)
{
if (!v[i] && l[i]<=c)
c = l[x=i];
}
v[x] = ;
for (int i=;i<n;i++)
{
l[i] = min (l[i],l[x]+d[i][x]);
}
}
printf ("%d\n",l[]);
} return ;
}