首页 > 代码库 > 数据结构与算法问题 单源最短路径 浙大OJ
数据结构与算法问题 单源最短路径 浙大OJ
- 题目描述:
- 给你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
代码:
#include <iostream> using namespace std; const int max = 65535; typedef struct graph { int vex[1000]; int weight[1000][1000]; //路径长度 int cost[1000][1000]; //花费 int numvex, numedge; }graph; void create(graph * &g) //生成图 { int i,w,c,j,k; cin >> g->numvex >> g->numedge; for (i = 0; i < g->numvex; i++) for (j = 1; j <= g->numvex; j++) { g->weight[i][j] = max; g->cost[i][j] = max; } for (k = 0; k < g->numedge; k++) { cin >> i >> j >> w >> c; g->weight[i][j] = w; g->cost[i][j] = c; g->weight[j][i] = g->weight[i][j]; g->cost[j][i] = g->cost[i][j]; } } void mydijkstra(graph * &g,int start,int end) //Dijkstra算法 { int mark1[1000],mark2[1000]; int dist1[1000],dist2[1000]; int i, j, k1,k2, min1,min2; for (i = 1; i <= g->numvex; i++) { dist1[i] = max; dist2[i] = max; } for (i = 1; i <= g->numvex; i++) { mark1[i] = 0; mark2[i] = 0; dist1[i] =g->weight[start][i]; dist2[i] = g->cost[start][i]; } mark1[start] = 1; mark2[start] = 1; dist1[start] = max; dist2[start] = max; for (i = 1; i < g->numvex; i++) { min1 = max; min2 = max; j = 1; while (j <= g->numvex) { if (!mark1[j] && dist1[j] < min1) { min1= dist1[j]; k1= j; } if (!mark2[j] && dist2[j] < min2) { min2 = dist2[j]; k2= j; } j++; } mark1[k1] = 1; dist1[k1] = min1; mark2[k2] = 1; dist2[k2] = min2; for (j = 1; j <= g->numvex; j++) { if (!mark1[j] && dist1[j] > dist1[k1] + g->weight[k1][j]) dist1[j] = dist1[k1] + g->weight[k1][j]; if (!mark2[j] && dist2[j] > dist2[k2] + g->cost[k2][j]) dist2[j] = dist2[k2] + g->cost[k2][j]; } } cout << dist1[end]; cout << " "; cout << dist2[end]; } int main() { int start, end; graph *g = new graph; create(g); cin >> start >> end; if (start == 0 & end == 0) return 0; mydijkstra(g, start, end); system("pause"); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。