遂溪网站开发公司,专业推广公司,flash xml网站模板,首码圈项目网题目详情#xff1a;
有了一张自驾旅游路线图#xff0c;你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序#xff0c;帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的#xff0c;那么需要输出最便宜的…题目详情
有了一张自驾旅游路线图你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的那么需要输出最便宜的一条路径。
输入格式:
输入说明输入数据的第1行给出4个正整数N、M、S、D其中N2≤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;
}
