http://acm.hdu.edu.cn/showproblem.php?pid=2066
今天复习了一下最短路和最小生成树,发现居然闹了个大笑话-----我居然一直写的是Floyd,但我自己一直以为这是Dijkstra---我居然一直把两个算法
记的是混的,还居然一直没有被别人发现,真是个大乌龙
好了,看看这道题,赤裸裸的最短路水题,首先来个Floyd的,把城市看成点,将连通的的点赋值为给定的时间,未连通的赋值为很大,这是个无向的关系
然后就是三个循环,以一个点为媒介,把每个点遍历一遍,比较找出点连通的最小值就行,稍微优化一点点就不会超时了
code
#include<cstdio>
#include<algorithm>
#define inf 1000000005
using namespace std;
int mp[][],q[];
void jjc()
{
int i,j;
for (i=;i<=;i++){
for (j=;j<=;j++){
if (i==j) mp[i][j]=;
else mp[i][j]=inf;
}
}
}
int min(int x,int y){
if (x<y) return x;
else return y;
}
int main()
{
int t,s,d,c,i,j,k,w,mx,a,b,mn;
while (~scanf("%d %d %d",&t,&s,&d))
{
jjc();
mx=;mn=inf;
while (t--)
{
scanf("%d %d %d",&a,&b,&c);
if (mp[a][b]>c)
mp[a][b]=mp[b][a]=c;
if (a>mx) mx=a; 没有给定范围,所以找范围
if (b>mx) mx=b;
if (a<mn) mn=a;
if (b<mn) mn=b;
}
for (k=mn;k<=mx;k++){
for (i=mn;i<=mx;i++){
if (mp[i][k]>=inf) continue; //稍微优化一点点
for (j=mn;j<=mx;j++){
mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
}
}
}
for (i=;i<=s;i++)
scanf("%d",&q[i]);
int ans=inf;
while (d--)
{
scanf("%d",&w);
for (i=;i<=s;i++)
{
if (mp[q[i]][w]<ans)
ans=mp[q[i]][w];
}
}
printf("%d\n",ans);
}
return ;
}
然后是Dijkstra的, Floyd是把任意两点的最短距离都求了出来,而Dijkstra只是求了特定的起点与所有点之间的最短路,一般情况而言,后者要快于前者,具体用哪种根据题目而定
按照距离从小到大的顺序,找出从给定起点能够到达的下一点,每找到一个这样的点,然后更新其余点之间的距离
code
#include<cstdio>
#define inf 100000005
using namespace std;
int map[][],vis[],dis[];
int st[],sr[];
int mn,mx;
int min(int x,int y)
{
if (x<y) return x;
else return y;
}
void jjc()
{
int i,j;
for (i=;i<=;i++){
for (j=;j<=;j++){
if (i==j) map[i][j]=;
else map[i][j]=inf;
}
}
}
void dijkstra(int x)
{
int i,pos,j,q;
for (i=mn;i<=mx;i++)
{
dis[i]=map[x][i];
vis[i]=;
}
vis[x]=;
for (i=mn;i<=mx;i++)
{
q=inf;pos=x;
for (j=mn;j<=mx;j++)
if (!vis[j]&&dis[j]<q)
{
pos=j;
q=dis[j];
}
vis[pos]=;
for (j=mn;j<=mx;j++)
dis[j]=min(dis[j],dis[pos]+map[pos][j]);
}
}
int main()
{
int t,s,d,a,b,c,i,j;
while (~scanf("%d %d %d",&t,&s,&d))
{
jjc();
mx=,mn=inf;
while (t--)
{
scanf("%d %d %d",&a,&b,&c);
if (map[a][b]>c)
map[a][b]=map[b][a]=c;
if (a>mx) mx=a;
if (b>mx) mx=b;
if (a<mn) mn=a;
if (b<mn) mn=b;
}
for (i=;i<=s;i++)
scanf("%d",&st[i]);
for (i=;i<=d;i++)
scanf("%d",&sr[i]);
int ans=inf;
for (i=;i<=s;i++)
{
dijkstra(st[i]);
for (j=;j<=d;j++)
if (dis[sr[j]]<ans)
ans=dis[sr[j]];
}
printf("%d\n",ans);
}
return ;
}
队列储存,广搜版的spfa
code
#include<cstdio>
#include<cstring>
#include<queue>
#define inf 0x3fffffff
using namespace std;
int map[][],vis[],dis[];
int st[],sr[];
int mn,mx,s,d;
void jjc()
{
int i,j;
for (i=;i<=;i++){
for (j=;j<=;j++){
if (i==j) map[i][j]=;
else map[i][j]=inf;
}
}
}
int spfa()
{
int num,i;
memset(vis,,sizeof(vis));
for (i=mn;i<=mx;i++)
dis[i]=inf;
queue<int> q;
for (i=;i<=s;i++)
{
dis[st[i]]=;
q.push(st[i]);
}
while(!q.empty())
{
num=q.front();
q.pop();
vis[num]=;
for (i=mn;i<=mx;i++)
{
if (dis[i]>dis[num]+map[num][i])
{
dis[i]=dis[num]+map[num][i];
if (vis[i]==)
{
vis[i]=;
q.push(i);
}
}
}
}
int p=inf;
for (i=;i<=d;i++)
{
if (p>dis[sr[i]]) p=dis[sr[i]];
}
return p;
}
int main()
{
int t,a,b,c,i,j;
while (~scanf("%d %d %d",&t,&s,&d))
{
jjc();
mx=,mn=inf;
while (t--)
{
scanf("%d %d %d",&a,&b,&c);
if (map[a][b]>c)
map[a][b]=map[b][a]=c;
if (a>mx) mx=a;
if (b>mx) mx=b;
if (a<mn) mn=a;
if (b<mn) mn=b;
}
for (i=;i<=s;i++)
scanf("%d",&st[i]);
for (i=;i<=d;i++)
scanf("%d",&sr[i]);
int ans=spfa();
printf("%d\n",ans);
}
return ;
}