最短路径问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13577 Accepted Submission(s): 4156
(1<n<=1000, 0<m<100000, s != t)
#include <stdio.h>
#include <string.h>
#define maxnum 1005
#define maxint 999999
int dist[maxnum],hua[maxnum],c[maxnum][maxnum],d[maxnum][maxnum];
int n;
void dijkstra(int x,int y)
{
int i,j;
bool v[maxnum]={0};
memset(dist,maxint,sizeof(dist));
memset(hua,maxint,sizeof(hua));
v[x]=1;
dist[x]=0;
hua[x]=0;
for(i=1;i<=n;i++)
{
int u=x;
int min=maxint;
for(j=1;j<=n;j++)
{
if(dist[j]<min&&!v[j])
{
min=dist[j];
u=j;
}
}
v[u]=1;
for(j=1;j<=n;j++)
{
if(!v[j]&&dist[j]>dist[u]+c[u][j])
{
dist[j]=dist[u]+c[u][j];
hua[j]=hua[u]+d[u][j];
}
if(!v[j]&&dist[j]==dist[u]+c[u][j]&&hua[j]>hua[u]+d[u][j])
{
hua[j]=hua[u]+d[u][j];
}
}
}
}
int main()
{
int m,x,y,p,q,k,a,b;
while(scanf("%d%d",&n,&m)&&(n&&m))
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
c[i][j]=maxint;
d[i][j]=maxint;
}
}
for(i=1;i<=m;i++)
{
scanf("%d%d%d%d",&x,&y,&p,&q);
if(p<c[x][y])
{
c[x][y]=p;
c[y][x]=p;
d[x][y]=q;
d[y][x]=q;
}
if(p==c[x][y]&&q<d[x][y])
{
d[x][y]=q;
d[y][x]=q;
}
}
scanf("%d%d",&a,&b);
dijkstra(a,b);
printf("%d %d\n",dist[b],hua[b]);
}
return 0;
}