PAT1030-Travel Plan
C语言源码：
[cpp]
#include<stdio.h>
#include<limits.h>
typedef struct node
{
int length,cost;
}node;
node A[600][600];
int visited[600];
node T[600];
int Stack[600][600];
int top[600];
int main()
{
int n,m,i,j,s,t,a,b,length,cost,minlength,mincost,fmin,k;
scanf("%d %d %d %d",&n,&m,&s,&t);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
A[i][j].length=INT_MAX;
visited[i]=0;
T[i].length=INT_MAX;
T[i].cost=INT_MAX;
top[i]=0;
}
for(i=0;i<m;i++)
{
scanf("%d %d %d %d",&a,&b,&length,&cost);
if(length<A[a][b].length||(length==A[a][b].length&&cost<A[a][b].cost))
{
A[a][b].length=length;
A[a][b].cost=cost;
}
A[b][a].length=A[a][b].length;
A[b][a].cost=A[a][b].cost;
}
visited[s]=1;
T[s].length=0;
T[s].cost=0;
i=s;
top[s]=1;
Stack[s][0]=s;
while(i!=t)
{
for(j=0;j<n;j++)
{
if(visited[j]==0)
{
if(A[i][j].length!=INT_MAX)
{
if(T[i].length+A[i][j].length<T[j].length||(T[i].length+A[i][j].length==T[j].length&&T[i].cost+A[i][j].cost<T[j].cost))
{
T[j].length=T[i].length+A[i][j].length;
T[j].cost=T[i].cost+A[i][j].cost;
top[j]=top[i];
for(k=0;k<top[i];k++)
Stack[j][k]=Stack[i][k];
}
}
}
}
minlength=INT_MAX;
mincost=INT_MAX;
for(j=0;j<n;j++)
{
if(visited[j]==0&&(T[j].length<minlength||(T[j].length==minlength&&T[j].cost<mincost)))
{
fmin=j;
minlength=T[j].length;
mincost=T[j].cost;
}
}
visited[fmin]=1;
Stack[fmin][top[fmin]++]=fmin;
i=fmin;
}
for(i=0;i<top[t];i++)
printf("%d ",Stack[t][i]);
printf("%d %d\n",T[t].length,T[t].cost);
return 0;
}
补充：软件开发 , C++ ,
