PTA 1030 Travel Plan

这篇具有很好参考价值的文章主要介绍了PTA 1030 Travel Plan。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

个人学习记录,代码难免不尽人意。

A traveler’s map gives the distances between cities along the highways, together with the cost of each highway. Now you are supposed to write a program to help a traveler to decide the shortest path between his/her starting city and the destination. If such a shortest path is not unique, you are supposed to output the one with the minimum cost, which is guaranteed to be unique.

Input Specification:
Each input file contains one test case. Each case starts with a line containing 4 positive integers N, M, S, and D, where N (≤500) is the number of cities (and hence the cities are numbered from 0 to N−1); M is the number of highways; S and D are the starting and the destination cities, respectively. Then M lines follow, each provides the information of a highway, in the format:

City1 City2 Distance Cost

where the numbers are all integers no more than 500, and are separated by a space.

Output Specification:
For each test case, print in one line the cities along the shortest path from the starting point to the destination, followed by the total distance and the total cost of the path. The numbers must be separated by a space and there must be no extra space at the end of output.

Sample Input:
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
Sample Output:
0 2 3 3 40

#include<cstdio>
#include<algorithm>
using namespace std;
int N,M,C1,C2;
const int maxn=510;


const int INF=1000000000;
bool vis[maxn]={false};
int d[maxn],c[maxn],pre[maxn];
struct node{
	int d;
	int cost;
};
node Node[maxn][maxn];
void dijkstra(){
	fill(d,d+maxn,INF);
	fill(c,c+maxn,INF);
	for(int i=0;i<N;i++) pre[i]=i;
	d[C1]=0;c[C1]=0;
	for(int i=0;i<N;i++){
		int u=-1;int min=INF;
		for(int j=0;j<N;j++){
			if(vis[j]==false&&d[j]<min){
				u=j;
				min=d[j];
			}
		}
	if(u==-1) return;
	vis[u]=true;
	for(int v=0;v<N;v++){
		if(vis[v]==false&&Node[u][v].d!=0){
			if(d[v]>Node[u][v].d+d[u]){
				d[v]=Node[u][v].d+d[u];
				c[v]=Node[u][v].cost+c[u];
				pre[v]=u;
			}else if(d[v]==Node[u][v].d+d[u]){
				if(c[v]>Node[u][v].cost+c[u]){
					c[v]=Node[u][v].cost+c[u];
					pre[v]=u;
				}
			}
		}
	}
	}
}
void DFS(int s){
	if(s==C1){
		printf("%d",s);
		return;
	}
	else{
		DFS(pre[s]);
		printf(" %d",s);
	}
}
int main(){
	scanf("%d%d%d%d",&N,&M,&C1,&C2);
	for(int i=0;i<M;i++){
		int cost,d;
		int c1,c2;
		scanf("%d%d%d%d",&c1,&c2,&d,&cost);
		node* n=new node;
		n->cost=cost;
		n->d=d;
		Node[c1][c2]=Node[c2][c1]=*n;
		
	} 
	dijkstra();
	DFS(C2);
	printf(" %d %d\n",d[C2],c[C2]);
} 

本题参考了《算法笔记》上面的dijkstra算法,对于求解这一类的最小值问题可以将dijkstra算法的模板背过,然后根据题意修改其内容即可。
除了上面这种做法还可以将第二类距离的求解从dijkstra算法中剥离出来,采用DFS方法来处理,比较简单,我觉得两种方法掌握一种即可。文章来源地址https://www.toymoban.com/news/detail-625740.html

到了这里,关于PTA 1030 Travel Plan的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Codeforces 1868C/1869E Travel Plan 题解 | 巧妙思路与 dp

    为了更好的阅读体验,请点击这里 题目链接:Travel Plan 题目大意: (n) 个点的完全二叉树,每个点可以分配 (1 sim m) 的点权,定义路径价值为路径中最大的点权,求所有路径的价值和。 对于任意长度(这里主要指包括几个节点)的路径 (t) ,最大点权不超过 (k) 的方案数

    2024年02月09日
    浏览(33)
  • 【算法导论】图论(图的基本概念,图上的深度优先搜索(DFS),广度优先搜索(BFS),最小生成树(MST)及Prim,Kruskal算法)

    图(Graph)是一种包含节点与节点的边的集合,记作G=(V,E),V是节点的集合,E是边的集合。 有向图 一个有向图G=(V,E),E中每个元素是V上的一个二值关系:一条从a出发的连向b的边e可以记作一个 有序 对e = (a,b) 。 无向图 一个无向图G=(V,E),E的每个元素e可以表示V上的一个 无序 对,记

    2024年02月03日
    浏览(52)
  • 【深度优先搜索】【图论】【树】2646. 最小化旅行的价格总和

    【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字 深度优先搜索 图论 树 现有一棵无向、无根的树,树中有 n 个节点,按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ,其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在

    2024年02月19日
    浏览(40)
  • C++/PTA 关于深度优先搜索和逆序对的题应该不会很难吧这件事

    背景知识 深度优先搜索与 DFS 序 深度优先搜索算法(DFS)是一种用于遍历或搜索树或图的算法。以下伪代码描述了在树 T 上进行深度优先搜索的过程: 令 r 为树 T 的根,调用 DFS(T, r, L) 即可完成对 T 的深度优先搜索,保存在链表 L 中的排列被称为 DFS 序。相信聪明的你已经发

    2024年02月05日
    浏览(37)
  • 每天一道leetcode:797. 所有可能的路径(图论&中等&深度优先遍历)

    给你一个有 n 个节点的 有向无环图(DAG) ,请你找出所有从节点 0 到节点 n-1 的路径并输出( 不要求按特定顺序 ) graph[i] 是一个从节点 i 可以访问的所有节点的列表(即从节点 i 到节点 graph[i][j] 存在一条有向边)。 n == graph.length 2 = n = 15 0 = graph[i][j] n graph[i][j] != i (即不存

    2024年02月12日
    浏览(65)
  • 【图论】图的存储--链式前向星存图法以及深度优先遍历图

    无向图 - 就是一种特殊的有向图 - 只用考虑有向图的存储即可 邻接矩阵 邻接表 邻接表 存储结构: (为每一个点开了一个单链表,存储这个点可以到达哪个点) 1 : 3-4-null 2 : 1-4-null 3 : 4-null 4 : null 插入一条新的边 比如要插一条边: 2-3 先找到 2 对应的 单链表 然后将 3 插入到单链表

    2024年04月14日
    浏览(46)
  • 【图论】【深度优先搜索】【换根法】2858. 可以到达每一个节点的最少边反转次数

    图论 深度优先搜索 有向图 无向图 树 给你一个 n 个点的 简单有向图 (没有重复边的有向图),节点编号为 0 到 n - 1 。如果这些边是双向边,那么这个图形成一棵 树 。 给你一个整数 n 和一个 二维 整数数组 edges ,其中 edges[i] = [ui, vi] 表示从节点 ui 到节点 vi 有一条 有向边

    2024年03月23日
    浏览(48)
  • 图论与算法(5)图的广度优先遍历应用

    树的广度优先遍历(Breadth-First Traversal),也称为层次遍历,是一种按层次顺序逐级访问树节点的遍历方式。在广度优先遍历中,先访问树的根节点,然后按照从上到下、从左到右的顺序逐层访问树的节点。 首先将树的根节点入队列,然后循环执行以下操作:出队列一个节点

    2024年02月08日
    浏览(46)
  • 每天一道leetcode:剑指 Offer 34. 二叉树中和为某一值的路径(中等&图论&深度优先遍历&递归)

    给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 树中节点总数在范围 [0, 5000] 内 -1000 = Node.val = 1000 -1000 = targetSum = 1000 使用递归深度优先遍历,使用前序遍历,在遍历途

    2024年02月12日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包