日志
hdu3790-----单源最短路径
|
这是去年的第四题，第一次做dij，而且还是变形，所以很纠结。
1.输入时要考虑重边情况。
2.另一道hdu1874就是dij，但是要注意判断自己到自己的情况。
3.记住需要哪些数组，循环的步骤和条件，今年很有可能再出这种题。
#include<stdio.h>
#include<string>
#define MAX 0x7fffffff
bool u[1002];
int g[1002][1002],ex[1002][1002];
int d[1002],p[1002];
int main()
{
int n,m,i,k;
int a,b,d1,p1,s,t;
int min_d,min_p;
while(scanf("%d%d",&n,&m),n||m)
{
memset(g,-1,sizeof(g));
while(m--)
{
scanf("%d%d%d%d",&a,&b,&d1,&p1);
if(g[a][b]==-1||g[a][b]>d1){g[a][b]=g[b][a]=d1;ex[a][b]=ex[b][a]=p1;}
else if(g[a][b]==d1&&ex[a][b]>p1)ex[a][b]=ex[b][a]=p1;
}
scanf("%d%d",&s,&t);
for(i=1;i<=n;i++){d[i]=g[s][i];p[i]=ex[s][i];u[i]=false;}
u[s]=true;
d[s]=p[s]=0;
while(1)
{
min_d=min_p=MAX;
k=s;
for(i=1;i<=n;i++)
{
if(!u[i]&&d[i]>0)
{
if(d[i]<min_d){k=i;min_d=d[k];}
else if(d[i]==min_d&&p[i]<min_p){k=i;min_p=p[k];}
}
}
u[k]=true;
if(k==t)break;
for(i=1;i<=n;i++)
if(!u[i]&&g[k][i]>0)
{
if(d[i]==-1||d[k]+g[k][i]<d[i]){d[i]=d[k]+g[k][i];p[i]=p[k]+ex[k][i];}
else if(d[k]+g[k][i]==d[i]&&p[k]+ex[k][i]<p[i])p[i]=p[k]+ex[k][i];
}
}
printf("%d %d\n",d[t],p[t]);
}
return 0;
}
