【Uva 11280 飞到弗雷德里顿】

·你可以尽情地坐飞机,但停留次数遭到限制。

·英文题,述大意:

      给出一张有向图,起点是输入的第一个城市,终点是输入的最后一个城市。给出q个询问,每个询问含一个t,表示中途最多经过个城市的情况下,起点到终点的最短路径长度(即费用)。

·分析:

     经过的点的次数被限制,我们不禁想到使用二元组:(u,t)来表示从起点到节点u最多途径t个点(包括起点)时的最短路径长度。

·BellMan-Ford算法的精髓:枚举每条边,对该边的两点进行路径更新。不要学习了SPFA就忘记了它是哪里来的。在这个算法中,为了保证找到最短路,需要反复更新n-1次。如果我们只更新t次呢(即1~n的循环进行t次)?那么可以使得一个点的从起点到它最优路径只经过t个点,这与我们的需要完美契合。

              

·我们只需要枚举从小到大停留次数t,然后不断地1~n循环,每次完成后记录当前限制下的最短路,那么这样的离线处理就可以完美解决询问了。

·代码来了。

 1 #include<bits/stdc++.h>
 2 #define go(i,a,b) for(int i=a;i<=b;i++)
 3 #define inf 1000000000
 4 using namespace std;string a,b;map<string,int>S;
 5 int _,T,n,m,q,u[1002],v[1002],w[1002],d[102][102];
 6 int main(){scanf("%d",&T);_=T;while(scanf("%d",&n),T--)
 7 {
 8     go(i,1,n)cin>>a,S[a]=i,d[i][0]=inf;scanf("%d",&m);d[1][0]=0;
 9     go(i,1,m)cin>>a>>b>>w[i],u[i]=S[a],v[i]=S[b];
10     go(t,1,n){go(i,1,n)d[i][t]=d[i][t-1];
11     go(i,1,m)d[v[i]][t]=min(d[v[i]][t],d[u[i]][t-1]+w[i]);}
12     scanf("%d",&q);if(_-T-1)puts("");printf("Scenario #%d\n",_-T);
13
14     while(q--){int t;scanf("%d",&t);
15         d[n][t=min(++t,n)]==inf?puts("No satisfactory flights"):
16         printf("Total cost of flight(s) is $%d\n",d[n][t]);}
17 }return 0;}//Paul_Guderian

·另外,使用Dijkstra算法是否可以呢?可以。同样是用f[u][t]表示到达u点已经途径t个城市。这道题的数据,SPFA、Bellman-Ford更加适合。大米饼代码又不小心达到了排名第一。

那些卑微却炫目的欢愉,只是往昔壮景的悲悯。---汪峰《一瞬间》
时间: 06-15

【Uva 11280 飞到弗雷德里顿】的相关文章

UVA 11280 - Flying to Fredericton(最短路)

UVA 11280 - Flying to Fredericton 题目链接 题意:给定一些国家,和两个国家间的花费,现在有一些询问,询问每次最多转k次飞机,最小花费 思路:dijkstra变形,多开一维表示转机次数即可 代码: #include <cstdio> #include <cstring> #include <vector> #include <queue> #include <iostream> #include <strin

uva 11280 状态压缩+最短路

题意:坐飞机从 a 地到 b 地 ,在最多停留s次时 , 最小花费是多少? 在题目给出的地点 , 是按从远到近给出的 , 并且给出的航班中 , 不会有从远地点到近地点的航班. 因此从这可以看出 , 题目给的图是一个DAG图 , 那么我们就能用toposort来找最短路. 注意: 会有重边 解法: 构造一个数组 d[i][j]  , 表示从开始点 s  到点 i , 在停留 j 次时的最小花费. 然后我们再求出这个图的toposort , 再求这个每一个点和其相邻点的距离. 代码: #includ

UVA - 11280 Flying to Fredericton(SPFA)

题目大意:给出N个点,M条线,Q个询问,问从起点到终点,最多经过k个点的最短线路 解题思路:spfa直接跑,然后纪录最短路的数组加一个维度,纪录经过几个点就可以了,还是挺水的 #include <cstdio> #include <cstring> #include <map> #include <iostream> #include <queue> using namespace std; #define N 110 #define M 101

记忆细胞

图说:10月6日,2014年诺贝尔生理学或医学奖颁奖典礼现场,大屏幕上的头像从左至右分别是约翰·奥基夫.梅-布里特·莫泽和爱德华·莫泽 图CFP 新民晚报·新民网“今年的诺贝尔生理学与医学奖获得者们,是因为发现了大脑内的定位系统,一种大脑中内置的‘GPS’,它让我们能够在空间中实现定位.换言之,我们能找到回家的路,并不仅仅因为你能看得见,而是因为脑里有着一种特殊功能的细胞,是它把你带回家中.”北京时间昨晚当2014年诺贝尔生理医学奖颁布时,复旦大学神经生物所研究员禹永春如此解读. 禹永春说:“关

Tarjan 联通图 Kuangbin 带你飞 联通图题目及部分联通图题目

Tarjan算法就不说了 想学看这 https://www.byvoid.com/blog/scc-tarjan/ https://www.byvoid.com/blog/biconnect/ 下面是几份基本的模版 首先是无向图割点桥的代码 下面的代码是用于求割点数目的 其中add_block[u] = x  表示删除u点之后增加的联通块个数.注意是增加的联通块个数 const int MAXN = 1010; const int MAXM = 10010; const int INF = 0x

UVa - 12451 - Let&#39;s call SPaDe a SPaDe

先上题目: Problem H: Let's call SPaDe a SPaDe Passing time, walking the passage, as you pass the String Parsing Department(abbreviated SPaDe), you pause, amazed at them by parsing strings way past midnight. At the SPaDe , they are overwhelmed with the st

这个夏天,飞到北纬18&deg;去玩海&mdash;&mdash;带着小样儿去三亚(二)

    自由行,顾名思义很自由,想去哪去哪,但是对于我们来说也可能意味着不知道该去哪,事先没有做准备,加上之前的两趟跟团游,该去的景点基本都去了一遍,这趟自由行要去哪儿反而没了目标,温度只有32°,却炎热无比,热带的阳光晒到身上,不一会儿就有点烫,这样的天气,将近十点左右,我们带着一大一下俩娃在酒店周边的旅行社询问可以参与的行程,基本上给我们的答复都是你们来得太晚了,要去景点?可以,明天请早!好吧,谁让我们把自由行履行得如此彻底呢,对于明天是否能早起,我依然不敢肯定,既然这样,不如自由得更彻底,

UVA - 590Always on the run(递推)

题目:UVA - 590Always on the run(递推) 题目大意:有一个小偷现在在计划着逃跑的路线,但是又想省机票费.他刚开始在城市1,必须K天都在这N个城市里跑来跑去,最后一天达到城市N,问怎样计划路线的得到最少的费用. 解题思路:一开始题目意思就理解有些问题. dp[k][i]:代表在第k天小偷从某一个城市(除了i)坐飞机飞到城市i(到达城市i也是在这一天).第k天的话,就看这一天坐哪个航班,加上之前的费用是最小的,就选这个方案.然后k+ 1天就又是由第k天推出来的. 状态转移方

一百元的智能家居——Asp.Net Mvc Api+讯飞语音+Android+Arduino

大半夜的,先说些废话提提神 如今智能家居已经不再停留在概念阶段,高大上的科技公司都已经推出了自己的部分或全套的智能家居解决方案,不过就目前的现状而言,大多还停留在展厅阶段,还没有广泛的推广起来,有人说最大的问题是标准不统一云云,但在我看来,最大的问题在于两个方面,一个是价格,一个是操作的简便性,技术上的问题并不是阻碍智能家居推广的核心因素. 再来说说最近很火很惹人爱的微软小娜,Cortana.本人作为微软的死忠,作为一名靠.Net混饭的屌丝程序男,自然是有一部撸妹的,并且在小娜推送当天更新了手机