首页 > 代码库 > 【Uva 11280 飞到弗雷德里顿】
【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更加适合。大米饼代码又不小心达到了排名第一。
那些卑微却炫目的欢愉，只是往昔壮景的悲悯。---汪峰《一瞬间》
【Uva 11280 飞到弗雷德里顿】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。