给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。 Input 输入n,m,点的编号是1~n,然后是m行,每行4个数 a,b,d,p,表示a和b之间有一条边,且其长度为d,花费为p。最后一行是两个数 s,t;起点s,终点。n和m为0时输入结束。 (1<n<=1000, 0<m<100000, s != t) Output 输出 一行有两个数, 最短距离及其花费。
这个是个最短路双权值模板,在最少距离的基础上面加了一个最少花费,开辟两个二维数组,一个保存距离的权值,一个保留花费的权值,距离为第一关键字,花费为第二关键字,当路径相同的时候,我们就比较第二关键字,如果花费少的话就要对花费来进行松弛
#include <stdio.h>
#include <string.h>
#define N 1010
#define inf 99999999
int book[N];
int e[N][N];//距离的邻接矩阵
int g[N][N];//花费的邻接矩阵
int dis[N];//起点到各点松弛的最小距离
int cost[N];//起点到各点松弛的最小花费
int n,m,start,end;
void init()
{
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(i==j)
e[i][j]=g[i][j]=0;//因为有了个花费,距离和花费都要赋初值
else
e[i][j]=g[i][j]=inf;//不通就赋值为无穷大
}
void dijkstra()
{
int min1,u,v;
memset(book,0,sizeof(book));
for(int i=1; i<=n; i++)
{
dis[i]=e[start][i];//
cost[i]=g[start][i];
}
book[start]=1;
for(int i=1; i<n; i++)
{
min1=inf;
for(int j=1; j<=n; j++)
{
if(book[j]==0&&dis[j]<min1)
min1=dis[u=j];
}
book[u]=1;
for(int v=1; v<=n; v++)
if(dis[v]>dis[u]+e[u][v])
{
dis[v]=dis[u]+e[u][v];//这里如果距离较小后对距离松弛了还需要对花费进行松弛
cost[v]=cost[u]+g[u][v];//花费松弛
}
else if(dis[v]==dis[u]+e[u][v]&&cost[v]>cost[u]+g[u][v])//这里考虑第二关键字花费
//如果距离相同了,要对花费进行比较松弛
cost[v]=cost[u]+g[u][v];
}}
int main()
{
int a,b,c,d;
while(~scanf("%d%d",&n,&m)&&(n||m))
{
init();
for(int i=1; i<=m; i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
if(e[a][b]>c)//在出现多条相同路径取最短距离的
{
e[a][b]=e[b][a]=c;//无向图
g[a][b]=g[b][a]=d;//花费
}
else if(e[a][b]==c&&g[a][b]<d)//这里得注意,当距离相同的时候我们要取最少花费
{g[a][b]=g[b][a]=d;
}
}
scanf("%d%d",&start,&end);
dijkstra();
printf("%d %d\n",dis[end],cost[end]);
}}