dijstra最短路径算法
：
| 9885560 | 2013-12-23 23:54:56 | Accepted | 3790 | 203MS | 8112K | 1343 B | C++ | 泽泽 |
#include<cstdio>
#include<cstring>
#define inf 0xffffff
int g[][];
int v[][];
void dijstra(int n,int a)
{
int used[],i,j,k,min,dis[],lowcost[];
memset(used,,sizeof(used));
for(i=;i<=n;i++)
{
dis[i]=g[i][a];
lowcost[i]=v[i][a];
}
used[a]=;
for(i=;i<=n;i++)
{
j=a;min=inf;
for(k=;k<=n;k++)
{
if(dis[k]<min&&!used[k])
min=dis[k],
j=k;
}
used[j]=;
for(k=;k<=n;k++)
{
if(g[k][j]+dis[j]<dis[k]&&!used[k])
{
g[a][k]=g[k][a]=dis[k]=g[k][j]+dis[j];
lowcost[k]=v[a][k]=v[k][a]=v[k][j]+v[j][a];
}
if(g[k][j]+dis[j]==dis[k]&&!used[k])
{
if(v[k][j]+lowcost[j]<lowcost[k])
{
lowcost[k]=v[k][a]=v[k][j]+v[j][a];
} }
}
} }
int main()
{
int n,m,i,j,a,b,s,vi;
while(scanf("%d %d",&n,&m)!=EOF)
{
if(!n&&!m)break;
for(i=;i<=n;i++)
{
for(j=;j<=n;j++)
{
g[i][j]=inf,v[i][j]=inf;
}
g[i][i]=;
}
for(i=;i<=m;i++)
{
scanf("%d %d %d %d",&a,&b,&s,&vi);
if(s<g[a][b]) {
g[a][b]=g[b][a]=s;
v[a][b]=v[b][a]=vi;
}
if(s==g[a][b]&&vi<v[a][b])
{
v[a][b]=v[b][a]=vi;
}
}
int start,end;
scanf("%d %d",&start,&end);
dijstra(n,start);
printf("%d %d\n",g[start][end],v[start][end]);
}
return ;
}