关键词：
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 7248 | Accepted: 2338 |
Description
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
Source
题意：有了油量限制，每个点加油价格不一样，对于每个询问求最少花费
一看到d[i][j]这样的状态表示，马上想到分层图最短路，有点类似DP的思想
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> using namespace std; typedef long long ll; const int N=1e3+5,M=1e4+5,V=105; int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f; } struct edge{ int v,ne,w; }e[M<<1]; int h[N],cnt=0; void ins(int u,int v,int w){ cnt++; e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt; cnt++; e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt; } int n,m,Q,u,v,w,p[N],c,st,ed; struct hn{ int u,d,f; bool operator <(const hn &rhs)const{return d>rhs.d;} hn(int a=0,int b=0,int c=0):u(a),d(b),f(c){} }; int d[N][V]; bool done[N][V]; void bfs(int c,int st,int ed){ memset(d,127,sizeof(d)); memset(done,0,sizeof(done)); priority_queue<hn> q; q.push(hn(st,0,0)); d[st][0]=0; while(!q.empty()){ hn x=q.top();q.pop(); int u=x.u,f=x.f,cost=x.d;//printf("bfs %d %d ",u,f); //if(done[u][f]) continue; done[u][f]=1; if(u==ed){printf("%d ",cost);return;} if(f+1<=c&&!done[u][f+1]&&d[u][f]+p[u]<d[u][f+1]){ d[u][f+1]=d[u][f]+p[u]; q.push(hn(u,d[u][f+1],f+1)); } for(int i=h[u];i;i=e[i].ne){ int v=e[i].v,w=e[i].w; if(f>=w&&!done[v][f-w]&&d[v][f-w]>cost){ d[v][f-w]=cost; q.push(hn(v,cost,f-w)); } } } printf("impossible "); } int main(){ n=read();m=read(); for(int i=0;i<n;i++) p[i]=read(); for(int i=1;i<=m;i++){ u=read();v=read();w=read(); ins(u,v,w); } Q=read(); for(int i=1;i<=Q;i++){ c=read();st=read();ed=read(); bfs(c,st,ed); } }
图论补完计划poj3635（最短路变形）
FullTank?TimeLimit:1000MS MemoryLimit:65536KTotalSubmissions:7427 Accepted:2399DescriptionAftergoingthroughthereceiptsfromyourcartripthroughEuropethissummer,yourealisedthatthegaspricesvaried 查看详情
poj3635fulltank?(代码片段)
【题解】 用dijkstra算法求最短路。同时考虑在每个节点加油（一单位）与否。【代码】1#include<iostream>2#include<map>3#include<cstring>4#include<string>5#include<queue>6usingnamespacestd;7#definemaxn10058#definemaxm10... 查看详情
p4568飞行路线分层图最短路(代码片段)
P4568飞行路线分层图最短路分层图最短路问题模型求最短路时，可有\(k\)次更改边权（减为0）思路在普通求\(Dijkstra\)基础上，\(dis[x][j]\)多开一维\(j\)以存已用了多少次机会，然后每次松弛时，做完普通松弛操作后，还要使用一次... 查看详情
最短路||分层图最短路(代码片段)
在对可以任选的一部分边或点有限制的时候，可以建分层图 HDU3499题意：n个城市有m条价格不同的航线，从s到t，可以选择一条边价格减半，求最小花费建两层图，每一层图里连边，两层图里连边#include<map>#include<queue>... 查看详情
hdu5669road（线段树建树）（分层图最短路）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5669【分析】线段树建树+分层图最短路 #include<cstdio>#include<map>#include<algorithm>#include<vector>#include<iostream>#include<set 查看详情
最短路合集（分层图最短路传递闭包路径还原k短路...）(代码片段)
...先队列版本已经烂大街了，这里就不贴了，而且在下面的分层图里有写1.普通线段树时间和内存均是优先队列优化版本的$frac12$intn,m;structedge intto,w,nxt; edge() edge(intt,intww,intnn)to=t,w=ww,nxt=nn;e[maxn<<1];inth 查看详情
bzoj_2662_[beijingwc2012]冻结_分层图最短路
BZOJ_2662_[BeiJingwc2012]冻结_分层图最短路Description “我要成为魔法少女！” “那么，以灵魂为代价，你希望得到什么？”“我要将有关魔法和奇迹的一切，封印于卡片之中„„” &nb... 查看详情
xdoj_1078_分层图最短路
http://acm.xidian.edu.cn/problem.php?id=1078 模版。 #include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<vector>#include<queue>#def 查看详情
hdu3499(分层图最短路or反向建图)(代码片段)
传送门方法一：分层图#include<bits/stdc++.h>#defineper(i,a,b)for(inti=a;i<=b;i++)#definemod1000000007usingnamespacestd;typedeflonglongll;constllinf=23333333333333333LL;constdoubleeps=1e-8;intT;intread() 查看详情
educationalcodeforcesround102e.minimumpath（分层图最短路）(代码片段)
参考博客：做法1做法2分层图最短路讲解：链接题意给出一个nnn个点mmm条边的带权无向联通图。定义一个经过kkk条边的路径的权重为∑i=1kwei−maxi=1kwei+mini=1kwei\\sum_i=1^kw_ei−\\max_i=1^kw_ei+\\min_i=1^k... 查看详情
bzoj2763[jloi2011]飞行路线[分层图最短路]
2763:[JLOI2011]飞行路线TimeLimit: 10Sec MemoryLimit: 128MBSubmit: 2523 Solved: 946[Submit][Status][Discuss]DescriptionAlice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在n 查看详情
小雨坐地铁分层图最短路(代码片段)
... 因为有转车和车费逐步增加的情况存在 很容易想到分层图的概念 通过把路线看作不同的图层 就能把转车的概念转化为层与层之间的转化概念 令图层层数为0~m 其中第m层为中转线 所有的 查看详情
分层图最短路（dp思想）bzoj2662[beijingwc2012]冻结
2662:[BeiJingwc2012]冻结TimeLimit:3Sec MemoryLimit:128MBSubmit:999 Solved:535[Submit][Status][Discuss]Description “我要成为魔法少女！” “那么，以灵魂为代价，你希望得到什么？”“我要将有关魔法和奇迹的 查看详情
[codevs1912]汽车加油行驶问题（分层图最短路）
传送门 吐槽：神tm网络流 dis[i][j][k]表示到(i,j)还有k油的最优解然后跑spfa，中间分一大堆情况讨论1.当前队头还有油 1.目标点有加油站——直接过去 2.目标点每加油站——1.直接过去 ... 查看详情
p1073最优贸易分层图最短路(代码片段)
题目描述CC国有nn个大城市和mm 条道路，每条道路连接这 nn个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 mm 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向... 查看详情
bzoj1579:[usaco2009feb]revampingtrails道路升级--分层图最短路
1579:[Usaco2009Feb]RevampingTrails道路升级TimeLimit: 10Sec MemoryLimit: 64MBDescription每天,农夫John需要经过一些道路去检查牛棚N里面的牛.农场上有M(1<=M<=50,000)条双向泥土道路,编号为1..M.道路i连接牛棚P1_i和P2_i(1<=P1_i 查看详情
「jloi2011」「luogup4568」飞行路线（分层图最短路(代码片段)
题目描述Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在nn个城市设有业务，设这些城市分别标记为00到n-1n−1，一共有mm种航线，每种航线连接两个城市，并且航线有一定的价格。Alice和Bo... 查看详情
2018icpc南京网络赛-lmagicalgirlhaze(分层图最短路)(代码片段)
题意：有向图，可以把k条路的长度变为0，求1到n的最短路思路：将图复制k份，一共k+1层图，对于每一条i→j,都连一条低层的i→高层的j，并且权值为0即对每一对<i,j,w>，都加边<i,j,w>,<i+n,j+n,w>,<i+2n,j+2n,w>,....,... 查看详情