今天做了一道关于最短路径的算法题，虽然最后AC了，但是我写的第一个算法，我认为是没有问题的，自己编写的测试用例也全部通过，反复调试了，都没有错误。可是在OJ上一提交就提示Wrong Answer，真是苦闷啊！希望看到这篇文章的同志们给些提示。
两个算法都是用邻接表存储图的，都是比较纯粹的自定义结构体，使用的是DijkStra算法。虽然用容器也可以实现邻接表，但是个人感觉用结构体是比较简单，可以不用了解底层的实现。但是本人就是喜欢钻研一些基础的东西，无它，兴趣使然。
- 题目描述：
- 给你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 21 2 5 62 3 4 51 30 0
- 样例输出：
-
9 11
第一个算法---为啥子错撒？
#include#include #define MAXVALUE 999999;#define MAX_VERTEX_NUM 1001#define MAX_EDGE_NUM 100001using namespace std; struct ArcNode{ int vertex; int len; int cost; ArcNode *nextarc;}; typedef struct VertexNode{ ArcNode *firstArc; int size;}VNode[MAX_VERTEX_NUM]; struct Graph{ VNode nodes; int n, e;};int dist[MAX_VERTEX_NUM];int cost[MAX_VERTEX_NUM];bool visited[MAX_VERTEX_NUM];//Edge edges[MAX_EDGE_NUM];void allocateArcNode(ArcNode** arcNode){ *arcNode = (ArcNode*)malloc(sizeof(ArcNode)); (*arcNode)->nextarc = NULL;} void initeGraph(Graph &graph){ for (int i = 1; i <= MAX_VERTEX_NUM; i++) { graph.nodes[i].firstArc = NULL; graph.nodes[i].size = 0; } graph.n = 0; graph.e = 0;} void createGraph(Graph &graph, int m){ int v1, v2, len, cost; ArcNode* p1 = NULL; ArcNode* p2 = NULL; for (int i = 1; i <= m; i++) { allocateArcNode(&p1); allocateArcNode(&p2); cin >> v1 >> v2 >> len >> cost; p1->vertex = v2; p1->len = len; p1->cost = cost; p1->nextarc = graph.nodes[v1].firstArc; graph.nodes[v1].firstArc = p1; graph.nodes[v1].size++; p2->vertex = v1; p2->len = len; p2->cost = cost; p2->nextarc = graph.nodes[v2].firstArc; graph.nodes[v2].firstArc = p2; graph.nodes[v2].size++; }} //void printGraph(const Graph& graph, int n)//{// for (int i = 1; i <= n; i++)// {// ArcNode* arcPtr = graph.nodes[i].firstArc;//// cout << i << ": ";// cout << "size:" << graph.nodes[i].size << endl;// while (arcPtr != NULL)// {// cout << arcPtr->len << ' ' << arcPtr->cost << ";";// arcPtr = arcPtr->nextarc;// }//// cout << endl;// }//} void dijkStra(const Graph &graph, int v0, int n){ int index = v0; for (int i = 1; i <= n; i++) { ArcNode *arcPtr = graph.nodes[index].firstArc; while (arcPtr != NULL) { int tmp = arcPtr->vertex; int len = arcPtr->len; int co = arcPtr->cost; if (visited[tmp] == false || dist[tmp] > dist[index] + len || (dist[tmp] == dist[index] + len && cost[tmp] > cost[index] + co)) { dist[tmp] = arcPtr->len; cost[tmp] = arcPtr->cost; } arcPtr = arcPtr->nextarc; } int minLen = MAXVALUE; int minCost = MAXVALUE; for (int j = 1; j <= n; j++) { if (visited[j] == false && (dist[j] < minLen || (dist[j] == minLen && cost[j] < minCost))) { minLen = dist[j]; index = j; } } visited[index] = true; }} void freeSpaceOfGraph(Graph& graph){ for (int i = 1; i <= graph.n; i++) { ArcNode *arcPtr = graph.nodes[i].firstArc; while (arcPtr != NULL) { ArcNode *tmp = arcPtr; arcPtr = arcPtr->nextarc; delete tmp; } }} int main(){ int n, m; while (cin >> n >> m) { if (n == 0 && m == 0) break; int start, end; for (int i = 1; i <= n; i++) { visited[i] = false; cost[i] = MAXVALUE; dist[i] = MAXVALUE; } Graph graph; initeGraph(graph); graph.n = n; graph.e = m; createGraph(graph, m); cin >> start >> end; dijkStra(graph, start, n); cout << dist[end] << ' ' << cost[end] << endl; freeSpaceOfGraph(graph); } return 0;}
第二算法---完美AC
#include#include #define MAXVALUE 123123123#define MAX_VERTEX_NUM 1001#define MAX_EDGE_NUM 100001using namespace std; struct ArcNode{ int vertex; int len; int cost; ArcNode *nextarc;}; typedef struct VertexNode{ ArcNode *firstArc; int size;}VNode[MAX_VERTEX_NUM]; struct Graph{ VNode nodes; int n, e;};int dist[MAX_VERTEX_NUM];int cost[MAX_VERTEX_NUM];bool visited[MAX_VERTEX_NUM];//Edge edges[MAX_EDGE_NUM];void allocateArcNode(ArcNode** arcNode){ *arcNode = (ArcNode*)malloc(sizeof(ArcNode)); (*arcNode)->nextarc = NULL;} void initeGraph(Graph &graph){ for (int i = 1; i <= MAX_VERTEX_NUM; i++) { graph.nodes[i].firstArc = NULL; graph.nodes[i].size = 0; } graph.n = 0; graph.e = 0;} void createGraph(Graph &graph, int m){ int v1, v2, len, cost; ArcNode* p1 = NULL; ArcNode* p2 = NULL; for (int i = 1; i <= m; i++) { allocateArcNode(&p1); allocateArcNode(&p2); cin >> v1 >> v2 >> len >> cost; p1->vertex = v2; p1->len = len; p1->cost = cost; p1->nextarc = graph.nodes[v1].firstArc; graph.nodes[v1].firstArc = p1; graph.nodes[v1].size++; p2->vertex = v1; p2->len = len; p2->cost = cost; p2->nextarc = graph.nodes[v2].firstArc; graph.nodes[v2].firstArc = p2; graph.nodes[v2].size++; }} //void printGraph(const Graph& graph, int n)//{// for (int i = 1; i <= n; i++)// {// ArcNode* arcPtr = graph.nodes[i].firstArc;//// cout << i << ": ";// cout << "size:" << graph.nodes[i].size << endl;// while (arcPtr != NULL)// {// cout << arcPtr->len << ' ' << arcPtr->cost << ";";// arcPtr = arcPtr->nextarc;// }//// cout << endl;// }//} void dijkStra(const Graph &graph, int v0, int n){ int index = v0; dist[v0] = 0; cost[v0] = 0; visited[v0] = true; for (int i = 1; i <= n; i++) { ArcNode *arcPtr = graph.nodes[index].firstArc; while (arcPtr != NULL) { int tmp = arcPtr->vertex; int len = arcPtr->len; int co = arcPtr->cost; if ((visited[tmp] == false) && (dist[tmp] > dist[index] + len || (dist[tmp] == dist[index] + len && cost[tmp] > cost[index] + co))) { dist[tmp] = dist[index] + len; cost[tmp] = cost[index] + co; } arcPtr = arcPtr->nextarc; } int minLen = MAXVALUE; int minCost = MAXVALUE; for (int j = 1; j <= n; j++) { if (visited[j] == true || dist[j] == MAXVALUE) continue; if (dist[j] < minLen || (dist[j] == minLen && cost[j] < minCost)) { minLen = dist[j]; minCost = cost[j]; index = j; } } visited[index] = true; }} void freeSpaceOfGraph(Graph& graph){ for (int i = 1; i <= graph.n; i++) { ArcNode *arcPtr = graph.nodes[i].firstArc; while (arcPtr != NULL) { ArcNode *tmp = arcPtr; arcPtr = arcPtr->nextarc; delete tmp; } }} int main(){ int n, m; while (cin >> n >> m) { if (n == 0 && m == 0) break; int start, end; for (int i = 1; i <= n; i++) { visited[i] = false; cost[i] = MAXVALUE; dist[i] = MAXVALUE; } Graph graph; initeGraph(graph); graph.n = n; graph.e = m; createGraph(graph, m); cin >> start >> end; dijkStra(graph, start, n); cout << dist[end] << ' ' << cost[end] << endl; freeSpaceOfGraph(graph); } return 0;} /************************************************************** Problem: 1008 User: 凌月明心 Language: C++ Result: Accepted Time:10 ms Memory:1528 kb****************************************************************/