关键词：
After going through the receipts from your car trip through Europe this summer, you realised that the gas prices varied between the cities you visited. Maybe you could have saved some money if you were a bit more clever about where you filled your fuel?
To help other tourists (and save money yourself next time), you want to write a program for finding the cheapest way to travel between cities, filling your tank on the way. We assume that all cars use one unit of fuel per unit of distance, and start with an empty gas tank.
Input
The first line of input gives 1 ≤ n ≤ 1000 and 0 ≤ m ≤ 10000, the number of cities and roads. Then follows a line with n integers 1 ≤ pi ≤ 100, where pi is the fuel price in the ith city. Then follow m lines with three integers 0 ≤ u, v < n and 1 ≤ d ≤ 100, telling that there is a road between u and v with length d. Then comes a line with the number 1 ≤ q ≤ 100, giving the number of queries, and q lines with three integers 1 ≤ c ≤ 100, s and e, where c is the fuel capacity of the vehicle, s is the starting city, and e is the goal.
Output
For each query, output the price of the cheapest trip from s to e using a car with the given capacity, or "impossible" if there is no way of getting from s to e with the given car.
Sample Input
5 5 10 10 20 12 13 0 1 9 0 2 8 1 2 1 1 3 11 2 3 7 2 10 0 3 20 1 4
Sample Output
170 impossible
因为状态数只有n*100=10W 所以放心的爆搜就好了 ，，自己太蠢 爆搜都不敢写‘’
#include<cstdio>
#include<cstring>
#include<queue>
const int N=1010;
using namespace std;
struct Edge{
int v,w,next;
}e[20010];
int tot,head[N];
void add(int u,int v,int w){
e[tot].w=w;
e[tot].v=v;
e[tot].next=head[u];
head[u]=tot++;
}
int n,m,p[N],x,y,z,dp[N][110],c,s,t;
bool vis[N][110];
struct Node{
int u,cost,oil;
Node(){}
Node(int a,int b,int c):u(a),cost(b),oil(c){}
bool operator<(const Node &A)const{
return cost>A.cost;
}
};
void bfs(){
memset(dp,0x3f,sizeof(dp));
memset(vis,0,sizeof(vis));
dp[s][0]=0;
priority_queue<Node>Q;
Q.push(Node(s,0,0));
while(!Q.empty()){
Node now=Q.top();Q.pop();
int o=now.oil,u=now.u,cost=now.cost;
vis[u][o]=1;
if(u==t) {
printf("%d ",cost);
return ;
}
if(o+1<=c&&!vis[u][o+1]&&dp[u][o]+p[u]<dp[u][o+1]) {
dp[u][o+1]=dp[u][o]+p[u];
Q.push(Node(u,dp[u][o+1],o+1));
}
for(int i=head[u];i+1;i=e[i].next){
int v=e[i].v,w=e[i].w;
if(o>=w&&!vis[v][o-w]&&cost<dp[v][o-w]){
dp[v][o-w]=cost;
Q.push(Node(v,dp[v][o-w],o-w));
}
}
}
puts("impossible");
}
int main(){
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i) scanf("%d",p+i);
for(int i=1;i<=m;++i) {
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
int T;
for(scanf("%d",&T);T--;){
scanf("%d%d%d",&c,&s,&t);
bfs();
}
}
poj1442blackbox(优先队列）
题目地址：POJ1442这题是用了两个优先队列，当中一个是较大优先。还有一个是较小优先。让较大优先的队列保持k个。每次输出较大优先队列的队头。每次取出一个数之后，都要先进行推断，假设这个数比較大优先的队列的队头... 查看详情
poj2431（优先队列）
Agroupofcowsgrabbedatruckandventuredonanexpeditiondeepintothejungle.Beingratherpoordrivers,thecowsunfortunatelymanagedtorunoverarockandpuncturethetruck‘sfueltank.Thetrucknowleaksoneunitoffueleveryunit 查看详情
poj3253fencerepair优先队列
poj3253FenceRepair优先队列Description FarmerJohnwantstorepairasmalllengthofthefencearoundthepasture.Hemeasuresthefenceandfindsthatheneeds N (1≤ N ≤20,000)planksofwood,eachhavingsomein 查看详情
poj2431优先队列
Agroupofcowsgrabbedatruckandventuredonanexpeditiondeepintothejungle.Beingratherpoordrivers,thecowsunfortunatelymanagedtorunoverarockandpuncturethetruck‘sfueltank.Thetrucknowleaksoneunitoff 查看详情
poj2431（优先队列）
...的解法，所以应该没有问题。这道题是利用数据结构中的优先队列完成的。。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出（firstin,largestout）的行为特征。本来优... 查看详情
poj3431expedition优先队列
poj3431Expedition优先队列题目链接：http://poj.org/problem?id=2431思路：优先队列。对于一段能够达到的距离，优先选择其中能够加油最多的站点，这样，行驶过这段距离之后还能走更远的距离。将输入的数据进行排序处理，按照位置的... 查看详情
poj3635fulltank?
FullTank?TimeLimit:1000MS MemoryLimit:65536KTotalSubmissions:7543 Accepted:2444DescriptionAftergoingthroughthereceiptsfromyourcartripthroughEuropethissummer,yourealisedthatthegaspricesvaried 查看详情
usacomilkrouting///优先队列广搜(代码片段)
...C则这条边上花费时间为L+X/C求从点1到点n的最小花费 优先队列维护L+X/C最小广搜到点n#include<bits/stdc++.h>usingnamespacestd;#defineLLlonglong#defineINF0x3f3f3f3f#definemem(i,j)memset(i,j,sizeof(i))#defineinc(i,l,r)for(inti=l;i<=r;i++)#definedec(i,r,l)for(int... 查看详情
优先队列poj3253fencerepair
FenceRepairTimeLimit: 2000MS MemoryLimit: 65536KTotalSubmissions: 51411 Accepted: 16879DescriptionFarmerJohnwantstorepairasmalllengthofthefencearoundthepasture.Hemeasures 查看详情
acm/icpc2018亚洲区预选赛北京赛站网络赛a.savingtangmonkii（优先队列广搜）(代码片段)
#include<bits/stdc++.h>usingnamespacestd;constintmaxN=123;constintinf=1e9+7;charG[maxN][maxN];inttimes[maxN][maxN][6];intn,m,sx,sy,ex,ey,ans;intdir[4][2]=0,1,1,0,0,-1,-1,0;structnodei 查看详情
poj1442(treap||优先队列)
BlackBoxTimeLimit:1000MS MemoryLimit:10000KB 64bitIOFormat:%I64d&%I64uSubmitStatusDescriptionOurBlackBoxrepresentsaprimitivedatabase.Itcansaveanintegerarrayandhasaspecialivariable.Atthei 查看详情
poj3069（贪心+巧用优先队列）
...找最少的标记点数，很好理解，贪心嘛，由于最近正在看优先队列，突然感觉这题也能用优先队列做，就实践了一发，也过了;话不多说上码：CODE：1# 查看详情
poj3687：labelingballs（优先队列+拓扑排序）
id=3687">LabelingBallsTimeLimit:1000MSMemoryLimit:65536KTotalSubmissions:10178Accepted:2815DescriptionWindyhasNballsofdistinctweightsfrom1unittoNunits.Nowhetriestolabelthemwith1toNinsuchawaythat:Notwo 查看详情
poj-1475pushingboxes
...什么人的位置,箱子的位置啦,推了几次啊,走了几步啊用个优先队列好像会快很多在加个最优性剪枝好像就更快了(不加就死循环了)然后就没啥了 花絮:震惊!某学生被续走两天的时间!原因竟是........优先队列没有清空辣鸡多组... 查看详情
poj1862stripies优先队列
...进行碰撞结合，能够得到最小的质量。所有只要维护一个优先队列就可以了#include<iostream>#include<cstdio>#include<queue>#include< 查看详情
poj3614sunscreen(优先队列)
...将所有符合最小值小于等于该防晒霜的奶牛的最大值放入优先队列之中。然后优先队列是小值先出，所以 查看详情
poj1862stripies哈夫曼/贪心/优先队列
StripiesTimeLimit: 1000MS MemoryLimit: 30000KTotalSubmissions: 18198 Accepted: 8175DescriptionOurchemicalbiologistshaveinventedanewveryusefulformoflifecalledstripies(infa 查看详情
poj3253fencerepair哈夫曼树+优先队列
DescriptionFarmerJohnwantstorepairasmalllengthofthefencearoundthepasture.Hemeasuresthefenceandfindsthatheneeds N (1≤ N ≤20,000)planksofwood,eachhavingsomeintegerlength Li 查看详情