浙大数据结构第七周之07-图6 旅游规划

题目详情：

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

输入格式:

输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。

输出格式:

在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

输入样例:

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

输出样例:

3 40

主要思路：

就是Dijkstra的变形

代码实现：

#include <stdio.h>
#include <stdlib.h>
#define MAX_NODE_NUMS 505
#define NONE -1
#define INF 100000
#define TRUE 1
#define FALSE 0
typedef int bool;
typedef struct MatrixGraphNode MatrixGraphNode;
typedef MatrixGraphNode* MGraph;
struct MatrixGraphNode {int VertexNums, EdgeNums;int Distance[MAX_NODE_NUMS][MAX_NODE_NUMS];int Fare[MAX_NODE_NUMS][MAX_NODE_NUMS];
};
MGraph CreateEmptyGraph(int vertexNums, int edgeNums) {MGraph graph = (MGraph)malloc(sizeof(MatrixGraphNode));graph->VertexNums = vertexNums;graph->EdgeNums = edgeNums;for(int i = 0; i < vertexNums; i++) {for(int j = 0; j < vertexNums; j++) {if(i == j) {graph->Distance[i][i] = 0;graph->Fare[i][i] = 0;}else {graph->Distance[i][j] = INF;graph->Fare[i][j] = INF;}}}return graph;
}
void InsertEdge(int start, int end, int distance, int fare, MGraph graph) {graph->Distance[start][end] = distance; graph->Distance[end][start] = distance;graph->Fare[start][end] = fare; graph->Fare[end][start] = fare;return;
} 
MGraph BuildGraph(int vertexNums, int edgeNums) {MGraph graph = CreateEmptyGraph(vertexNums, edgeNums);int start, end, distance, fare;for(int i = 0; i < edgeNums; i++) {scanf("%d %d %d %d", &start, &end, &distance, &fare);InsertEdge(start, end, distance, fare, graph);}return graph;
}
int FindNearest(MGraph graph, int vis[], int start) {/*先找距离最近，距离同样近找最省钱*/int ret = NONE;int minDis = INF;int minFare = INF;for(int i = 0; i < graph->VertexNums; i++) {if(i != start && vis[i] == FALSE) {if(graph->Distance[start][i] < minDis) {ret = i;minDis = graph->Distance[start][i];minFare = graph->Fare[start][i];}else if(graph->Distance[start][i] == minDis) {if(graph->Fare[start][i] < graph->Fare[start][ret]) {ret = i;minDis = graph->Distance[start][i];minFare = graph->Fare[start][i];}}}}return ret;
}
void Dijksta(MGraph graph, int start, int end) {int path[MAX_NODE_NUMS];int vis[MAX_NODE_NUMS];int dis[MAX_NODE_NUMS];int fare[MAX_NODE_NUMS];/*初始化*/for(int i = 0; i < graph->VertexNums; i++) {vis[i] = FALSE;if(i != start) {if(graph->Distance[start][i] < INF) {path[i] = start;dis[i] = graph->Distance[start][i];fare[i] = graph->Fare[start][i];}else {path[i] = NONE;dis[i] = INF;fare[i] = INF;}}}path[start] = NONE;dis[start] = 0;fare[start] = 0;while(TRUE) {int nearest = FindNearest(graph, vis, start);if(nearest == NONE) {break;}vis[nearest] = TRUE;for(int i = 0; i < graph->VertexNums; i++) {if(i != nearest && vis[i] == FALSE && graph->Distance[nearest][i] < INF) {if(graph->Distance[nearest][i] < 0) {return;}else if(dis[nearest] + graph->Distance[nearest][i] < dis[i]) {path[i] = nearest;dis[i] = dis[nearest] + graph->Distance[nearest][i];fare[i] = fare[nearest] + graph->Fare[nearest][i];}else if(dis[nearest] + graph->Distance[nearest][i] == dis[i]) {if(fare[nearest] + graph->Fare[nearest][i] < fare[i]) {path[i] = nearest;fare[i] = fare[nearest] + graph->Fare[nearest][i];}}}} }printf("%d %d", dis[end], fare[end]);
} 
int main() {int vertexNums, edgeNums, startPoint, endPoint;scanf("%d %d %d %d", &vertexNums, &edgeNums, &startPoint, &endPoint);MGraph graph = BuildGraph(vertexNums, edgeNums);Dijksta(graph, startPoint, endPoint);free(graph);return 0;
}