最短路径问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13771 Accepted Submission(s): 4234
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 输出 一行有两个数， 最短距离及其花费。
Sample Input
3 2
1 2 5 6
2 3 4 5
1 3
0 0
Sample Output
9 11
Source 浙大计算机研究生复试上机考试-2010年 这道题我竟然在INFINITY这个点wa了许久，例子：#define INFINITY 0x7fffffff 那么INFINITY + any < 0 成为一个极小的数，那么结果自然就是错的
/******************************
*
*acm: hdu-3790
*
*title: 最短路径问题
*
*time : 2014.8.29
*
*******************************/
/*
思路： 1/2
例图 ① -> ②
2/2↘ ↙1/2 (距离/花费)
③
可见，路径相等时，记录花费较少的即可，可直接用Dijkstra算法。
*/
#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 1001
#define MAXEDGE 100000
#define INFINITY 0x3fffffff
//不能0x7fffffff => 加上1变成负数 成了一个很小的数
//构造边集
typedef struct Edge
{
int cost; //花费
int lenth; //长度
} Edge;
Edge edges[MAXVEX][MAXVEX];
void CreateMGraph(int numVertexes, int numEdges)
{
int i, j;
int a, b;
int len, cost;
for (i = 1; i <= numVertexes; i++)
{
for (j = 1; j <= numVertexes; j++)
{
edges[i][j].lenth = INFINITY;
edges[i][j].cost = INFINITY;
}
}
for (i = 0; i < numEdges; i++)
{
scanf("%d%d%d%d", &a, &b, &len, &cost);
if (edges[a][b].lenth > len)
{
edges[a][b].lenth = len;
edges[a][b].cost = cost;
edges[b][a].lenth = len;
edges[b][a].cost = cost;
}
else if (edges[a][b].lenth == len)
{
if (edges[a][b].cost > cost)
{
edges[a][b].cost = cost;
edges[b][a].cost = cost;
}
}
}
/* 静态数据
edges[1][2].lenth = 5;
edges[1][2].cost = 6;
edges[2][1].lenth = 5;
edges[2][1].cost = 6;
edges[2][3].lenth = 4;
edges[2][3].cost = 5;
edges[3][2].lenth = 4;
edges[3][2].cost = 5;
*/
}
typedef int ShortPathTable[MAXVEX];
typedef int Cost[MAXVEX];
//Dijkstra算法
void ShortestPath_Dijkstra(int numVertexes, int numEdges, int v0, int vm, int *len, int *cost)
{
int v, w, k, min;
int min_cost;
ShortPathTable D;
int final[MAXVEX]; //标记是否求得顶点v0-vm的路径
Cost C;
*len = INFINITY;
*cost = INFINITY;
for (v = 1; v <= numVertexes; v++)
{
final[v] = 0;
D[v] = edges[v0][v].lenth;
C[v] = edges[v0][v].cost;
}
final[v0] = 1;
//开始主循环，每次求得v0到某v顶点的最短路径
for (v = 2; v <= numVertexes; v++)
{
min = INFINITY; //当前所知离v0顶点的最近距离
min_cost = 0;
for (w = 1; w <= numVertexes; w++) //寻找离v0最近的顶点
{
if (!final[w] && D[w] < min)
{
k = w;
min = D[w]; //w顶点离v0更近
min_cost = C[w];
}
}
final[k] = 1;
if (k == vm)
{
*len = D[k];
*cost = C[k];
break;
}
for (w = 1; w <= numVertexes; w++)
{
if (!final[w] && (min+edges[k][w].lenth) < D[w]) //如果经过v顶点的路径比现在这条路径的长度短的话
{
//说明找到了更短的路径，修改D[w],C[w]
D[w] = min + edges[k][w].lenth;
C[w] = min_cost + edges[k][w].cost;
}
else if (!final[w] && (min+edges[k][w].lenth) == D[w]) //如果经过v顶点的路径与现在这条路径相等
{
if (min_cost + edges[k][w].cost < C[w]) //取花费较少的值赋值
{
C[w] = min_cost + edges[k][w].cost;
}
}
}
}
}
int main()
{
int numVertexes = 3;
int numEdges = 2;
int start;
int end;
int len;
int cost;
while (scanf("%d%d", &numVertexes, &numEdges) && numVertexes != 0 && numVertexes != 0)
{
CreateMGraph(numVertexes, numEdges);
scanf("%d%d", &start, &end);
ShortestPath_Dijkstra(numVertexes, numEdges, start, end, &len, &cost);
printf("%d %d\n", len, cost);
}
return 0;
}