关键词：
【题解】
用dijkstra算法求最短路。同时考虑在每个节点加油（一单位）与否。
【代码】
1 #include <iostream> 2 #include <map> 3 #include <cstring> 4 #include <string> 5 #include <queue> 6 using namespace std; 7 #define maxn 1005 8 #define maxm 10005 9 10 /* 11 * dp[i][j] denodes the least cost on the ith node 12 * with j oil left. 13 */ 14 int price[maxn], dp[maxn][105], vis[maxn][105]; 15 int Ecnt, capacaity, sp, ep; 16 17 struct Node 18 19 int node, cost, oil; 20 Node(int n, int c, int o) : 21 node(n), cost(c), oil(o) 22 bool operator < (const Node &N) const 23 return cost > N.cost; 24 25 ; 26 27 struct Edge 28 29 int node; 30 int len; 31 Edge* next; 32 edges[2*maxm]; 33 34 Edge* head[maxn]; 35 36 void init() 37 38 Ecnt = 0; 39 fill(head, head + maxn, (Edge*)0); 40 41 42 void build(int u, int v, int w) 43 44 edges[Ecnt].node = u; 45 edges[Ecnt].len = w; 46 edges[Ecnt].next = head[v]; 47 head[v] = edges + Ecnt++; 48 49 edges[Ecnt].node = v; 50 edges[Ecnt].len = w; 51 edges[Ecnt].next = head[u]; 52 head[u] = edges + Ecnt++; 53 54 55 void dijkstra() 56 57 memset(vis, 0, sizeof(vis)); 58 memset(dp, 1, sizeof(dp)); 59 priority_queue<Node> pq; 60 pq.push(Node(sp, 0, 0)); 61 dp[sp][0] = 0; 62 while (!pq.empty()) 63 Node np = pq.top(); 64 pq.pop(); 65 int n = np.node, c = np.cost, o = np.oil; 66 vis[n][o] = 1; 67 if (n == ep) 68 printf("%d ", c); 69 return; 70 71 /* decide to add oil or not */ 72 if (o + 1 <= capacaity && !vis[n][o + 1] && dp[n][o] + price[n] < dp[n][o + 1]) 73 dp[n][o + 1] = dp[n][o] + price[n]; 74 pq.push(Node(n, dp[n][o + 1], o + 1)); 75 76 /* drive to the next node */ 77 for (Edge *Ep = head[n]; Ep; Ep = Ep->next) 78 int N = Ep->node, Len = Ep->len; 79 if (o >= Len && !vis[N][o - Len] && c < dp[N][o - Len]) 80 dp[N][o - Len] = c; 81 pq.push(Node(N, dp[N][o - Len], o - Len)); 82 83 84 85 printf("impossible "); 86 return; 87 88 89 int main() 90 91 int city_n, road_m, queries; 92 cin >> city_n >> road_m; 93 init(); 94 for (int i = 0; i < city_n; i++) 95 cin >> price[i]; 96 for (int i = 0; i < road_m; i++) 97 int u, v, d; 98 cin >> u >> v >> d; 99 build(u, v, d); 100 101 cin >> queries; 102 for (int i = 0; i < queries; i++) 103 cin >> capacaity >> sp >> ep; 104 dijkstra(); 105 106 //system("pause"); 107 return 0; 108
poj3635fulltank?[分层图最短路]
FullTank?TimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 7248 Accepted: 2338DescriptionAftergoingthroughthereceiptsfromyourcartripthroughEuropethissummer,yourealis 查看详情
图论补完计划poj3635（最短路变形）
FullTank?TimeLimit:1000MS MemoryLimit:65536KTotalSubmissions:7427 Accepted:2399DescriptionAftergoingthroughthereceiptsfromyourcartripthroughEuropethissummer,yourealisedthatthegaspricesvaried 查看详情
poj3635优先队列+打标记+广搜
AftergoingthroughthereceiptsfromyourcartripthroughEuropethissummer,yourealisedthatthegaspricesvariedbetweenthecitiesyouvisited.Maybeyoucouldhavesavedsomemoneyifyouwereabitmorecleveraboutwhereyoufilled 查看详情
hdu3635(代码片段)
/*一开始第a个球在第a个城市操作Tab，把第a个球所在城市的所有球移到b所在的城市操作Qa要求输出第a个球在哪个城市第a个球所在的城市有几个球第a个球移动次数*/#include<iostream>#include<cstring>#include<cstdio>#definemovemovee#... 查看详情
hdu3635dragonballs（带权并查集）(代码片段)
DragonBallsTimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):10628 AcceptedSubmission(s):3802ProblemDescriptionFivehundredyearslater,thenumberofdragonballswillincreaseunexpectedly,soit‘stoodifficultforMonkeyKing... 查看详情
hdu-3635dragonballs并查集(代码片段)
题意：1~N个龙珠，放在1~N个城市，有两种操作：TAB将A所再城市的所有球转移到B所在的城市。QX询问X所在的城市pls，该城市中龙珠数量nm，以及龙珠转移次数trs题解：并查集模板题，顺带更新一些数据。pls不必更新，因为X所在的... 查看详情
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... 查看详情
3635转换成小写字母(代码片段)
给你一个字符串s，将该字符串中的大写字母转换成相同的小写字母，返回新的字符串。示例1：输入：s="Hello"输出："hello"示例2：输入：s="here"输出："here"示例3：输... 查看详情
poj1606poj3414(代码片段)
JugsDescriptionInthemovie"DieHard3",BruceWillisandSamuelL.Jacksonwereconfrontedwiththefollowingpuzzle.Theyweregivena3-gallonjuganda5-gallonjugandwereaskedtofillthe5-gallonjugwithex 查看详情
poj刷题指南(代码片段)
POJ刷题指南好久没写代码，编码能力退步了，后期争取每日一题，能刷多少是多少。OJ上的一些水题(可用来练手和增加自信)(poj3299(√),poj2159(√),poj2739(√),poj1083(√),poj2262(√),poj1503(√),poj3006(√),poj2255(√),poj3094(√))好... 查看详情
hdu3635dragonballs(带权并查集)
...#20540;是该城市的龙珠数。times[x]为该龙珠运输了多少次。代码例如以下：#inclu 查看详情
poj~1904(代码片段)
DescriptionOnceuponatimetherelivedakingandhehadNsons.AndtherewereNbeautifulgirlsinthekingdomandthekingknewabouteachofhissonswhichofthosegirlshedidlike.Thesonsofthekingwereyoungandlight-headed,soitwasp 查看详情
poj2236并查集(代码片段)
poj2236DescriptionAnearthquaketakesplaceinSoutheastAsia.TheACM(AsiaCooperatedMedicalteam)havesetupawirelessnetworkwiththelapcomputers,butanunexpectedaftershockattacked,allcomputersinthenetworkwereallb 查看详情
[poj3904]skycode(代码片段)
[POJ3904]SkyCode题面Stanculikesspacetravelsbutheisapoorsoftwaredeveloperandwillneverbeabletobuyhisownspacecraft.ThatiswhyheispreparingtostealthespacecraftofPetru.Thereisonlyoneproblem–Petruhaslockedthes 查看详情
poj-3450(代码片段)
题目链接：http://poj.org/problem?id=3450CorporateIdentityTimeLimit: 3000MS MemoryLimit: 65536KTotalSubmissions: 8549 Accepted: 2856DescriptionBesideotherservices,ACMhelpscompa 查看详情
poj3087(代码片段)
http://poj.org/problem?id=3087Shuffle‘mUpTimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 13803 Accepted: 6356DescriptionAcommonpastimeforpokerplayersatapokertablei 查看详情