题目要求先选最短的道路，如果没有最短路可选，即几条道路都相等，再考花费。用Dijkstra更快一些。在选出最短边的同时加上对应的花费就可以了。详细请看代码：
#include
#include
#include
using namespace std;
#define MAX 1002
#define inf 999999
int map[MAX][MAX],cost[MAX][MAX];
int n;
void DJ(int st,int en)//Dijkstra 传入起点和终点
{
int i,j,MIN,v;
int flag[MAX],dis[MAX],value[MAX];
for(i=1;i<=n;i++)
{
dis[i]=map[st][i];
value[i]=cost[st][i];//与一般模板相似，多加一个花费而已
}
memset(flag,0,sizeof(flag));
flag[st]=1;
for(i=1;i<=n;i++)
{
MIN=inf;
for(j=1;j<=n;j++)
{
if(!flag[j]&&MIN>dis[j])
{
v=j;
MIN=dis[j];
}
}
if(MIN==inf)break;
flag[v]=1;
for(j=1;j<=n;j++)
{
if(!flag[j]&&map[v][j]dis[v]+map[v][j])
{
dis[j]=dis[v]+map[v][j];
value[j]=value[v]+cost[v][j];//先选好边长，同时也把对应的花费加上
}
else
if(dis[j]==dis[v]+map[v][j])//如果路长相等，则优先花费小的
{
if(value[j]>value[v]+cost[v][j])
value[j]=value[v]+cost[v][j];
}
}
}
}
cout<
|