最短路 floyed

2024-04-12 10:58
文章标签 短路 floyed

本文主要是介绍最短路 floyed,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

今天开始学学最短路 现在从最开始的开始学 floyed(0(n3))

感觉floyed 有动态规划的思想

通过枚举来把到每个点的最小价格算出来 然后保存到数组中

上例题 hdu 1690 Bus System

Bus System

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 10298    Accepted Submission(s): 2810


 

Problem Description

Because of the huge population of China, public transportation is very important. Bus is an important transportation method in traditional public transportation system. And it’s still playing an important role even now.
The bus system of City X is quite strange. Unlike other city’s system, the cost of ticket is calculated based on the distance between the two stations. Here is a list which describes the relationship between the distance and the cost.
 



Your neighbor is a person who is a really miser. He asked you to help him to calculate the minimum cost between the two stations he listed. Can you solve this problem for him?
To simplify this problem, you can assume that all the stations are located on a straight line. We use x-coordinates to describe the stations’ positions.

 

 

Input

The input consists of several test cases. There is a single number above all, the number of cases. There are no more than 20 cases.
Each case contains eight integers on the first line, which are L1, L2, L3, L4, C1, C2, C3, C4, each number is non-negative and not larger than 1,000,000,000. You can also assume that L1<=L2<=L3<=L4.
Two integers, n and m, are given next, representing the number of the stations and questions. Each of the next n lines contains one integer, representing the x-coordinate of the ith station. Each of the next m lines contains two integers, representing the start point and the destination.
In all of the questions, the start point will be different from the destination.
For each case,2<=N<=100,0<=M<=500, each x-coordinate is between -1,000,000,000 and 1,000,000,000, and no two x-coordinates will have the same value.

 

 

Output

For each question, if the two stations are attainable, print the minimum cost between them. Otherwise, print “Station X and station Y are not attainable.” Use the format in the sample.

 

 

Sample Input

 

2 1 2 3 4 1 3 5 7 4 2 1 2 3 4 1 4 4 1 1 2 3 4 1 3 5 7 4 1 1 2 3 10 1 4

 

 

Sample Output

 

Case 1: The minimum cost between station 1 and station 4 is 3. The minimum cost between station 4 and station 1 is 3. Case 2: Station 1 and station 4 are not attainable.

 

上代码:

#include<bits/stdc++.h>
using namespace std;
#define INF -1
long long int l1,l2,l3,l4,c1,c2,c3,c4,n,m,x,y,a[505],vis[505][505];
long long  check(long long int x)//按规则返回要用多少钱 
{if(x<=l1) return c1;else if(x<=l2) return c2;else if(x<=l3) return c3;else if(x<=l4) return c4;else return INF;
}
int main() 
{int t,l=1;cin>>t;while(t--){cin>>l1>>l2>>l3>>l4>>c1>>c2>>c3>>c4;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){vis[i][j]=INF;}//初始化 for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)//枚举 {if(i==j) vis[i][j]=0;//终点站与起点站一致就是没坐车 不用花钱 else vis[i][j]=check(abs(a[i]-a[j]));//要花的钱数 }for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(vis[i][k]!=INF&&vis[k][j]!=INF)//这条路可以走 不是死胡同 {if(vis[i][k]+vis[k][j]<vis[i][j]||vis[i][j]==-1)//i直接到j的价格比i到k再到j的价格大 或者 i不能直接到j  vis[i][j]=vis[i][k]+vis[k][j];//就把最小值赋给i到j的价格 }//从i到j的这个路程 选出最小的价格 }//有动态规划的思想 cout<<"Case "<<l++<<":"<<endl;while(m--){cin>>x>>y;if(vis[x][y]==INF)//如果还是不能到达 printf("Station %d and station %d are not attainable.\n",x,y);else//能到达的最小路径 printf("The minimum cost between station %d and station %d is %I64d.\n",x,y,vis[x][y]);		}}} 

 

这篇关于最短路 floyed的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/896937

相关文章

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1502 MPI Maelstrom(单源最短路dijkstra)

题目真是长得头疼,好多生词,给跪。 没啥好说的,英语大水逼。 借助字典尝试翻译了一下,水逼直译求不喷 Description: BIT他们的超级计算机最近交货了。(定语秀了一堆词汇那就省略吧再见) Valentine McKee的研究顾问Jack Swigert,要她来测试一下这个系统。 Valentine告诉Swigert:“因为阿波罗是一个分布式共享内存的机器,所以它的内存访问

poj 3159 (spfa差分约束最短路) poj 1201

poj 3159: 题意: 每次给出b比a多不多于c个糖果,求n最多比1多多少个糖果。 解析: 差分约束。 这个博客讲差分约束讲的比较好: http://www.cnblogs.com/void/archive/2011/08/26/2153928.html 套个spfa。 代码: #include <iostream>#include <cstdio>#i

hdu 3790 (单源最短路dijkstra)

题意: 每条边都有长度d 和花费p,给你起点s 终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。 解析: 考察对dijkstra的理解。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin

poj 3255 次短路(第k短路) A* + spfa 或 dijkstra

题意: 给一张无向图,求从1到n的次短路。 解析: A* + spfa 或者 dijkstra。 详解见上一题:http://blog.csdn.net/u013508213/article/details/46400189 本题,spfa中,stack超时,queue的效率最高,priority_queue次之。 代码: #include <iostream>#i

poj 2449 第k短路 A* + spfa

poj 2449: 题意: 给一张有向图,求第k短路。 解析: A* + spfa。 一下转自:http://blog.csdn.net/mbxc816/article/details/7197228 “描述一下怎样用启发式搜索来解决K短路。 首先我们知道A*的基础公式:f(x)=g(x)+h(x);对h(x)进行设计,根据定义h(x)为当前的x点到目标点t所需要的实际距

poj 3259 最短路负环

John的农场里N块地,M条路连接两块地,W个虫洞,虫洞是一条单向路,会在你离开之前把你传送到目的地,就是当你过去的时候时间会倒退Ts。我们的任务是知道会不会在从某块地出发后又回来,看到了离开之前的自己。简化下,就是看图中有没有负权环。有的话就是可以,没有的话就是不可以了。 import java.io.BufferedReader;import java.io.InputStream;

POJ1724最短路

n个点,拥有总的价值money m条边(u,v,len ,cost),长度len,代价cost 求不超过money的代价条件下最短路。 public class Main {public static void main(String[] args) {new Task().solve();}}class Task {InputReader in = new InputReader

【AcWing】851. 求最短路

spfa算法其实是对贝尔曼福特算法做一个优化。 贝尔曼福特算法会遍历所有边来更新,但是每一次迭代的话我不一定每条边都会更新,SPFA是对这个做优化。 如果说dist[b]在当前这次迭代想变小的话,那么一定是dist[a]变小了,只有a变小了,a的后继(b)才会变小。 用宽搜来做优化,用一个队列,队列里边存的就是所有变小了的结点(队列里存的是待更新的点)。 基本思路就是我更新过谁,我再拿