正文 

当前位置： 首页 > java > java教程

poj3635fulltank?

嘒彼小星 嘒彼小星     2022-09-17     395

关键词：

Full Tank?
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 7543   Accepted: 2444

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

Nordic 2007
 
【题解】
设b[i][j]表示在第i个城市，剩余汽油j的答案
每次选答案最小的去拓展，拓展方案无非两种：买1个汽油或者走向下一个城市
注意如果新的方案答案比已有答案小，就不再加入优先队列了
其实出队的节点b[i][j]，一定是最优的
很（一点也不）显然，没有更小的值去更新b[i][j]了，只能用b[i][j]去更新别人
很想dijkstra
复杂度O(n*clogn*c)
 
技术分享 
  1 #include <iostream>
  2 #include <cstdlib>
  3 #include <cstring>
  4 #include <cstdio>
  5 #include <algorithm>
  6 #include <queue>
  7 
  8 inline void read(int &x)
  9 {
 10     x = 0;char ch = getchar(), c = ch;
 11     while(ch < ‘0‘ || ch > ‘9‘)c = ch, ch = getchar();
 12     while(ch <= ‘9‘ && ch >= ‘0‘)x = x * 10 + ch - ‘0‘, ch = getchar();
 13     if(c == ‘-‘)x = -x;
 14 } 
 15 
 16 const int MAXN = 2000 + 10;
 17 const int MAXM = 20000 + 10;
 18 const int MAXC = 200 + 10;
 19 
 20 struct Edge
 21 {
 22     int u,v,w,next;
 23     Edge(int _u, int _v, int _w, int _next){u = _u;v = _v; w = _w; next = _next;}
 24     Edge(){}
 25 }edge[MAXM << 2];
 26 int head[MAXN], cnt;
 27 
 28 inline void insert(int a, int b, int c)
 29 {
 30     edge[++cnt] = Edge(a,b,c,head[a]);
 31     head[a] = cnt;
 32 }
 33 
 34 int n,m,value[MAXN],qq,b[MAXN][MAXC],s,e,c;
 35 
 36 struct Node
 37 {
 38     int now, v, ans;
 39     Node(){}
 40     Node(int _now, int _v, int _ans){now = _now;v = _v; ans = _ans;}
 41 };
 42 
 43 struct cmp
 44 {
 45     bool operator()(Node a, Node b)
 46     {
 47         return a.ans > b.ans;
 48     }
 49 };
 50 
 51 std::priority_queue<Node, std::vector<Node>, cmp> q;
 52 
 53 void bfs(int s, int e)
 54 {
 55     memset(b, 0x3f, sizeof(b));
 56     while(q.size())q.pop();
 57     q.push(Node(s, 0, 0));
 58     b[0][0] = 1;
 59     if(s == e)
 60     {
 61         printf("0
");
 62         return;
 63     }
 64     register Node tmp;
 65     while(q.size())
 66     {
 67         tmp = q.top();q.pop();
 68         if(tmp.v + 1 <= c && b[tmp.now][tmp.v + 1] > tmp.ans + value[tmp.now])q.push(Node(tmp.now, tmp.v + 1, tmp.ans + value[tmp.now])), b[tmp.now][tmp.v + 1] = tmp.ans + value[tmp.now];
 69         for(register int pos = head[tmp.now];pos;pos = edge[pos].next)
 70         {
 71             if(tmp.v < edge[pos].w || b[edge[pos].v][tmp.v - edge[pos].w] <= tmp.ans)continue;
 72             if(edge[pos].v == e)
 73             {
 74                 printf("%d
", tmp.ans);
 75                 return;
 76             }
 77             q.push(Node(edge[pos].v, tmp.v - edge[pos].w, tmp.ans));
 78             b[edge[pos].v][tmp.v - edge[pos].w] =  tmp.ans;
 79         }
 80     }
 81     printf("impossible
");
 82 }
 83 
 84 int main()
 85 {
 86     read(n);read(m);
 87     register int tmp1, tmp2, tmp3;
 88     for(register int i = 1;i <= n;++ i)read(value[i]);
 89     for(register int i = 1;i <= m;++ i)
 90     {
 91         read(tmp1), read(tmp2), read(tmp3);
 92         insert(tmp1 + 1, tmp2 + 1, tmp3);
 93         insert(tmp2 + 1, tmp1 + 1, tmp3);
 94     }
 95     read(qq);
 96     for(;qq;-- qq)
 97     {
 98         read(c);read(s);read(e);
 99         ++ s;++ e;
100         bfs(s, e);
101     }
102     return 0;
103 }
POJ3635

 

 
 
 

poj3635fulltank?(代码片段)

【题解】    用dijkstra算法求最短路。同时考虑在每个节点加油（一单位）与否。【代码】1#include<iostream>2#include<map>3#include<cstring>4#include<string>5#include<queue>6usingnamespacestd;7#definemaxn10058#definemaxm10... 查看详情

图论补完计划poj3635（最短路变形）

FullTank?TimeLimit:1000MS MemoryLimit:65536KTotalSubmissions:7427 Accepted:2399DescriptionAftergoingthroughthereceiptsfromyourcartripthroughEuropethissummer,yourealisedthatthegaspricesvaried 查看详情

poj3635优先队列+打标记+广搜

AftergoingthroughthereceiptsfromyourcartripthroughEuropethissummer,yourealisedthatthegaspricesvariedbetweenthecitiesyouvisited.Maybeyoucouldhavesavedsomemoneyifyouwereabitmorecleveraboutwhereyoufilled 查看详情

poj2594treasureexploration

TreasureExplorationTimeLimit:6000MS MemoryLimit:65536KTotalSubmissions:8879 Accepted:3635DescriptionHaveyoueverreadanybookabouttreasureexploration?Haveyoueverseeanyfilmabouttreasureexplorati 查看详情

poj2506tiling

TilingTimeLimit:1000MS MemoryLimit:65536KTotalSubmissions:7437 Accepted:3635DescriptionInhowmanywayscanyoutilea2xnrectangleby2x1or2x2tiles?Hereisasampletilingofa2x17rectangle.InputInputisase 查看详情

uva11367fulltank?(dp+dijkstra)

题意：n个城市有m条道路。每个城市的油价不一样，给出起点s和终点t，以及汽车的油箱的容量，求从城市s到城市t的最便宜路径。析：dp[u][i]表示在第u个城市，还剩下iL升油，一开始用BFS，TLE，要注意效率，用dijkstra，找到城市t... 查看详情

hdu3635dragonballs（带权并查集）

题目链接：　　http://acm.hdu.edu.cn/showproblem.php?pid=3635题目描述：DragonBallsProblemDescriptionFivehundredyearslater,thenumberofdragonballswillincreaseunexpectedly,soit‘stoodifficultforMonkeyKing(WuKong)togat 查看详情

hdu3635dragonballs

DragonBallsTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):4165    AcceptedSubmission(s):1603ProblemDescriptionFiv 查看详情

hdu3635

题目链接：HDU-36351#include<cstdio>2#include<cstring>3constintmaxn=10010;4intf[maxn],ct[maxn],trans[maxn];5intn,m;6voidinit()7{8for(inti=0;i<=n;i++)9{10f[i]=i;11ct[i]=1;12trans[i]=0;13}14}15 查看详情

uvalive3635pie

https://vjudge.net/problem/UVALive-3635题意：有F+1个人要分n个蛋糕，他们得到的蛋糕的面积必须是一样的，但是每个蛋糕必须是整块的蛋糕，而不是有多块蛋糕拼成的，蛋糕的形状也可以不相同。给出n块蛋糕各自的半径，求他们每个人... 查看详情

hdu3635dragonballs(带权并查集)

题目地址：pid=3635">HDU3635加权并查集水题。用num数组维护该城市有多少龙珠，用times数组维护每一个龙珠运输了多少次。num数组在合并的时候维护。times数组因为每一个都不一样。所以要在找根的时候递归来所有维护。终于，x龙... 查看详情

hdu3635dragonballs(并查集)

DragonBallsTimeLimit:2000/1000ms(Java/Other)   MemoryLimit:32768/32768K(Java/Other)TotalSubmission(s):64   AcceptedSubmission(s):26Font: TimesNewRoman | Ve 查看详情

la3635派

题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1636题意：f+1个人，来分n个圆形派，每个人只能从一个派中拿，也就是说，不能从两个里面去拼。求每个人最大的面积。分析：二... 查看详情

hdu3635(代码片段)

/*一开始第a个球在第a个城市操作Tab，把第a个球所在城市的所有球移到b所在的城市操作Qa要求输出第a个球在哪个城市第a个球所在的城市有几个球第a个球移动次数*/#include<iostream>#include<cstring>#include<cstdio>#definemovemovee#... 查看详情

uvalive-3635-pie（二分）

题意：有F+1（1<=F<=10000）个人分N（1<=N<=10000）个圆形派，每个人得到的派面积相同，且必须是一整块（不能够两个甚至多个派拼在一起），求每个人最多能得到多大面积的派。（误差最多到0.001）因为答案是小数类型的... 查看详情

la3635pie(二分法)

链接：http://vjudge.net/problem/33697分析：二分答案。假设每个人得到派的最大面积是x，判断是否能满足F+1个人（因为派是不可以拼起来的，所以一个半径为r的派只能切出[πr²/x]个派，其他部分就浪费了）。1#include<cstdio>2#in... 查看详情

ob3635/ob2530pap/ob3398昂宝电子设计

OB3635MCPA 4-7X1W过认证 //QQ2892715427//输入电压：100-264VAC输入电流：＜0.1APF ＞0.5输出电压：12-25V输出电流：0.26-0.3A空载电压：＜40V 空载功率:＜0.1W 恒流精度： ±5%效率： ＞88% 启动时间：＜1S 耐压：... 查看详情

昂宝ob3635ampob33398mp大功率投光灯80w驱动照明

 昂宝OB3635AMP、OB33398MP大功率投光灯80W驱动照明、QQ 2892715427 InputCharacteristics ACinputvoltagerating100Vac~240Vac ACinputvoltagerange90Vac~264Vac ACinputfrequencyrange47Hz~63Hz1.2 查看详情