最短路径问题

[编程题]最短路径问题

热度指数：17467 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给你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)

输出描述:

输出 一行有两个数， 最短距离及其花费。

示例1

输入

输出

9 11

算法知识视频讲解

健康快乐最重要

发表于 2020-02-23 16:06:24

Dijkstra算法的应用总是爱犯的一个错误就是在构建图的时候总是构建单个边。害，应该两个边都加进去（因为是无向图）。 #include<iostream> #include<queue> #include<algorithm> #include<vecto 展开全文

rocsoft

发表于 2020-04-17 18:00:23

题目描述给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。输入描述输入n,m 点的编号是1-n,共m条边。然后是m行，每行4个数 a,b,d,p 表示a和b之间有一条展开全文

诗云panther

发表于 2021-08-19 19:56:10

include <stdio.h> include define N 26 using namespace std;struct Node{//二叉树节点 int p1;//第一个双亲的下标，-1表示不存在 int p2;//第二个双亲的下标，-1表示不存在}tree[N] 展开全文

GoodLunatic

发表于 2024-09-04 23:50:23

#include <iostream> #include <vector> #include <queue> #include <cstring> using namespace std; typedef pair<int, int>PII 展开全文

yyer

发表于 2023-03-09 21:10:37

#include <iostream> #include <queue> #include <cstring> #include <climits> #include <vector> using namespace std; const 展开全文

wbc990512

发表于 2021-01-24 17:37:35

一看到题就想到Dijkstra了。。但是突然看到两个权值懵逼了，看到讨论里面的大佬的代码才醒悟。题目输入比较坑的一点是，前面输入的边的距离和花费，到后面可能会变，比如前面输入了 1 2 8 6，后面又输入 2 1 2 9这种。所以在读入数据的时候（makeG函数），要判断一下。 Dijkstra 展开全文