多起点多终点 spfa(邻接矩阵模板)HDU 2066 一个人的旅行

2023-11-10 02:48

本文主要是介绍多起点多终点 spfa(邻接矩阵模板)HDU 2066 一个人的旅行,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一个人的旅行

TimeLimit: 1000/1000 MS (Java/Others)    Memory Limit:32768/32768 K (Java/Others)
Total Submission(s): 47739    Accepted Submission(s): 15834

ProblemDescription

虽然草儿是个路痴(就是在杭电待了一年多,居然还会在校园里迷路的人,汗~),但是草儿仍然很喜欢旅行,因为在旅途中 会遇见很多人(白马王子,^0^),很多事,还能丰富自己的阅历,还可以看美丽的风景……草儿想去很多地方,她想要去东京铁塔看夜景,去威尼斯看电影,去阳明山上看海芋,去纽约纯粹看雪景,去巴黎喝咖啡写信,去北京探望孟姜女……眼看寒假就快到了,这么一大段时间,可不能浪费啊,一定要给自己好好的放个假,可是也不能荒废了训练啊,所以草儿决定在要在最短的时间去一个自己想去的地方!因为草儿的家在一个小镇上,没有火车经过,所以她只能去邻近的城市坐火车(好可怜啊~)。

 

 

Input

输入数据有多组,每组的第一行是三个整数T,S和D,表示有T条路,和草儿家相邻的城市的有S个,草儿想去的地方有D个;
接着有T行,每行有三个整数a,b,time,表示a,b城市之间的车程是time小时;(1=<(a,b)<=1000;a,b之间可能有多条路)
接着的第T+1行有S个数,表示和草儿家相连的城市;
接着的第T+2行有D个数,表示草儿想去地方。

 

 

Output

输出草儿能去某个喜欢的城市的最短时间。

 

 

SampleInput

6 2 3

1 3 5

1 4 7

2 8 12

3 8 4

4 9 12

9 10 2

1 2

8 9 10

 

 

Sample Output

9

 

 

Author

Grass

 

 

Source

RPG专场练习赛

 

 

Recommend

Lcy

算法分析:

多起点多终点,可以把它们离草儿的城市为0,然后求每个的最短路,就是比较就是最短时间

代码实现:

 

#include<bits/stdc++.h>
#define N 1100  
#define INF 0x7ffffff  
using namespace std;  
int v[N],d[N],mp[N][N],n,s[N],t[N];  
int spfa(int S,int D)  
{  for(int i=1;i<=n;i++)  //赋初值{d[i]=INF;v[i]=0;}queue<int> q;  for(int i=0;i<S;i++)//多起点{  v[s[i]]=1;  d[s[i]]=0;  q.push(s[i]);  }  while(!q.empty()){  int c=q.front();  q.pop();  v[c]=0;  for(int i=1;i<=n;i++)  {  if(d[i]>d[c]+mp[c][i])  {  d[i]=d[c]+mp[c][i];  if(!v[i])   {v[i]=1;q.push(i);}}  }  }  int ans=INF;  for(int i=0;i<D;i++)    ans=min(ans,d[t[i]]);  return ans;  
}  int main()  
{  int m,S,D; while(~scanf("%d%d%d",&m,&S,&D))  {  for(int i=0;i<N;i++)//数组初始化for(int j=0;j<N;j++)  mp[i][j]=INF;  n=0;for(int i=0;i<m;i++)  {  int a,b,c;  scanf("%d%d%d",&a,&b,&c);  n=max(n,max(a,b));   //记录最大城市序号 if(c<mp[a][b])       //去重 ,这是邻接矩阵的好处mp[a][b]=mp[b][a]=c;  }  for(int i=0;i<S;i++)    scanf("%d",&s[i]);  for(int i=0;i<D;i++)    scanf("%d",&t[i]);  cout<<spfa(S,D)<<endl;  }  
}  

 

这篇关于多起点多终点 spfa(邻接矩阵模板)HDU 2066 一个人的旅行的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

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 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while