pku 3635 Full Tank? - bfs+优先队列
渐渐
posted @ 2010年9月26日 09:09
in ACM-图论
, 2697 阅读
题目大意：有N个站点，每个站点供应油的价格为Pi，有M条路，每条路耗油量为Ci。现在又Q个询问，求出，当坦克在S点，油量为0，要到达T点，油箱容量为V的最小价格。
分析：有点像dij，用一个数组used[ i ][ j ]记录，第i个站点，油量为j的情况是否出现过。用优先队列每次选出花费最小的节点更新。入队有2种情况：
1.当可以走向下一个节点时
2.当可以再买1升汽油时（保证每种情况都考虑到，DP的思想）
PS：代码写烂了...好慢
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | #include<iostream>#include<algorithm>#include<stdio.h>#include<string.h>#include<queue>#include<vector>using namespace std;#define MAXE 20020#define MAXN 1010#define SET(a,b) memset(a,b,sizeof(a))int next[MAXE],p[MAXE],c[MAXE],st[MAXN],e;int used[MAXN][110],price[MAXN];void add(int a,int b,int d){ next[e]=st[a]; p[e]=b; c[e]=d; st[a]=e++;}struct Node{ int num,fuel,cost; Node(int num,int fuel,int cost):num(num),fuel(fuel),cost(cost){} friend bool operator < (Node a,Node b) { return a.cost>b.cost; }};int work(int S,int T,int C){ priority_queue<Node> Q; SET(used,0); Q.push(Node(S,0,0)); used[S][0]=1; while(!Q.empty()) { int u=Q.top().num,f=Q.top().fuel,m=Q.top().cost; if(u==T)return m; Q.pop(); for(int v=st[u];v!=-1;v=next[v]) { if(f>=c[v]) { if(!used[p[v]][f-c[v]]) { used[p[v]][f-c[v]]=1; Q.push(Node(p[v],f-c[v],m)); } } } if(f+1<=C&&!used[u][f+1])Q.push(Node(u,f+1,m+price[u])); } return -1;}int main(){ int N,M; SET(st,-1);e=0; scanf("%d%d",&N,&M); int i,j,k; for(i=1;i<=N;i++)scanf("%d",price+i); for(i=1;i<=M;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); x++,y++; add(x,y,z); add(y,x,z); } int P; scanf("%d",&P); for(i=1;i<=P;i++) { int S,T,C; scanf("%d%d%d",&C,&S,&T); S++,T++; int tttt=work(S,T,C); if(tttt==-1)printf("impossible\n"); else printf("%d\n",tttt); } //system("pause"); return 0;} |
评论 (0)