原题链接：http://ac.jobdu.com/problem.php?pid=1008
- 题目描述：
-
给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。
- 输入：
-
输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点t。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)
- 输出：
-
输出 一行有两个数， 最短距离及其花费。
- 样例输入：
-
3 2
1 2 5 6
2 3 4 5
1 3
0 0
- 样例输出：
-
9 11
- 来源：2010年浙江大学计算机及软件工程研究生机试真题
- 题解：
- 这是一道简单的最短路径问题，唯一多出的是在最短路径基础上还有最小代价的限制。采用邻接表+迪杰斯特拉算法实现。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <stdlib.h>
using namespace std; #define MAX_VERTEX_NUM 1001
#define MAX_ARC_NUM 200001 /*******图的邻接表表示法**********/
typedef struct ArcNode
{
int adjvex; //该弧所指向顶点的位置
struct ArcNode *nextarc; //指向下一条弧的指针
int dist;
int cost;
}ArcNode; typedef struct VNode
{
int dist,cost;//起始点到当前这个点的距离和花费
ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct
{
AdjList vertices;//顶点数组
int vexnum;
int arcnum; //当前图的顶点数和弧数
}ALGraph; bool final[];
int a,b,d,c;
int s,t; int findNearest(ALGraph &G)
{
int i;
int min = INT_MAX;
int res = -;
int cnt=;
int arr[];
for(i = ; i<G.vexnum; i++)
if(G.vertices[i].dist<min && !final[i])
{
min = G.vertices[i].dist;
arr[cnt] = i;
cnt++;
}
min = INT_MAX;
if(cnt>)
{
for(i = ; i<cnt; i++)
if(G.vertices[arr[i]].cost<min)
{
min = G.vertices[arr[i]].cost;
res = arr[i];
}
}
return res;
}
void dij(ALGraph &G)
{
int i,w,j;
int min;
int near;
ArcNode *p,*q;
int v;
for(i = ; i<G.vexnum; i++)
G.vertices[i].dist = G.vertices[i].cost = INT_MAX; G.vertices[s-].dist = G.vertices[s-].cost = ; for (i=; i<G.vexnum;i++) //更新n-1次
{
min = INT_MAX;
near = findNearest(G);
if(near==-)
break;
final[near] = true; for (p=G.vertices[near].firstarc; p!=NULL; p=p->nextarc)
{
v = p->adjvex;
if(G.vertices[near].dist+p->dist<G.vertices[v].dist && !final[v])//更新节点
{
G.vertices[v].dist = G.vertices[near].dist+p->dist;
G.vertices[v].cost = G.vertices[near].cost+p->cost;
}
else if(G.vertices[near].dist+p->dist == G.vertices[v].dist && !final[v])//如果存在多条最短路径，更新最小花费节点
{
if(G.vertices[near].cost+p->cost<G.vertices[v].cost)
G.vertices[v].cost = G.vertices[near].cost+p->cost;
}
}
}//for
} int main()
{
// freopen("dij.in","r",stdin);
//freopen("dij.out","w",stdout);
ALGraph G;
ArcNode *p,*q;
int vexnum,arcnum;
//G = (ALGraph*)malloc(sizeof(ALGraph));
while(scanf("%d%d",&vexnum,&arcnum)!=EOF && (vexnum!= || arcnum!=) )
{
G.vexnum = vexnum;
G.arcnum = arcnum;
memset(final,,sizeof(final));
for(int i=; i<G.vexnum; i++)
G.vertices[i].firstarc = NULL;
for(int i=; i<G.arcnum; i++)
{
scanf("%d%d%d%d",&a,&b,&d,&c); if (G.vertices[a-].firstarc==NULL)
{
G.vertices[a-].firstarc = (ArcNode *)malloc(sizeof(ArcNode)); G.vertices[a-].firstarc->adjvex = b-;
G.vertices[a-].firstarc->dist = d;
G.vertices[a-].firstarc->cost = c;
G.vertices[a-].firstarc->nextarc = NULL;
}
else
{
for (p=G.vertices[a-].firstarc; p->nextarc!=NULL; p=p->nextarc); q = (ArcNode*)malloc(sizeof(ArcNode));
q->adjvex = b-;
q->dist = d;
q->cost = c;
q->nextarc = NULL; p->nextarc = q;
} }
scanf("%d%d",&s,&t);
dij(G);
printf("%d %d\n",G.vertices[t-].dist,G.vertices[t-].cost);
}
return ;
}