題目鏈接：http://poj.org/problem?id=3635

　　容易想到用二維數(shù)組記錄狀態(tài)求最短路，然后用優(yōu)先隊列優(yōu)化，類似于Dijkstra和BFS。我開始設(shè)計的過程是直接直接從當(dāng)前點向相鄰點轉(zhuǎn)移并找出所有可能狀態(tài)，結(jié)果TLE。貌似是無關(guān)狀態(tài)太多了，沒想到卡得這么緊。別人的做法是只考慮兩個狀態(tài)：1、加一單位油 2、向相鄰點移動；這樣就砍掉了一些對最優(yōu)解不必要的狀態(tài)。

1 //STATUS:C++_AC_297MS_2404KB 2 #include<stdio.h> 3 #include<stdlib.h> 4 #include<string.h> 5 #include<math.h> 6 #include<iostream> 7 #include<string> 8 #include<algorithm> 9 #include<vector> 10 #include<queue> 11 #include<stack> 12 using namespace std; 13 #define LL __int64 14 #define pdi pair<double,int> 15 #define Max(a,b) ((a)>(b)?(a):(b)) 16 #define Min(a,b) ((a)<(b)?(a):(b)) 17 #define mem(a,b) memset(a,b,sizeof(a)) 18 #define lson l,mid,rt<<1 19 #define rson mid+1,r,rt<<1|1 20 const int N=1010,M=1000000,INF=0x3f3f3f3f,MOD=1999997; 21 const LL LLNF=0x3f3f3f3f3f3f3f3fLL; 22 const double DNF=100000000; 23 24 struct Node{ 25 int d,u,c; 26 bool operator < (const Node &ths) const { 27 return d>ths.d; 28 } 29 }; 30 struct Edge{ 31 int u,v,w; 32 }e[N*20]; 33 int vis[N][110],d[N][110],w[N],first[N],next[N*20]; 34 int n,m,t,mt,cup; 35 36 void adde(int a,int b,int c) 37 { 38 e[mt].u=a,e[mt].v=b,e[mt].w=c; 39 next[mt]=first[a],first[a]=mt++; 40 e[mt].u=b,e[mt].v=a,e[mt].w=c; 41 next[mt]=first[b],first[b]=mt++; 42 } 43 44 int Dijkstra(int s,int end) 45 { 46 int i,j,k,dis,u,v,c; 47 Node t; 48 priority_queue<Node> q; 49 mem(vis,0); 50 mem(d,INF); 51 d[s][0]=0; 52 q.push(Node{0,s,0}); 53 while(!q.empty()){ 54 t=q.top();q.pop(); 55 u=t.u;c=t.c; 56 if(u==end)return t.d; 57 if(vis[u][c])continue; 58 vis[u][c]=1; 59 if(c<cup && t.d+w[u]<d[u][c+1]){ 60 d[u][c+1]=t.d+w[u]; 61 q.push(Node{d[u][c+1],u,c+1}); 62 } 63 for(i=first[u];i!=-1;i=next[i]){ 64 v=e[i].v; 65 if(c>=e[i].w && d[u][c]<d[v][c-e[i].w]){ 66 d[v][c-e[i].w]=d[u][c]; 67 q.push(Node{d[u][c],v,c-e[i].w}); 68 } 69 } 70 } 71 return -1; 72 } 73 74 int main() 75 { 76 // freopen("in.txt","r",stdin); 77 int i,j,a,b,c,ans; 78 while(~scanf("%d%d",&n,&m)) 79 { 80 mt=0; 81 mem(first,-1); 82 for(i=0;i<n;i++) 83 scanf("%d",&w[i]); 84 for(i=0;i<m;i++){ 85 scanf("%d%d%d",&a,&b,&c); 86 adde(a,b,c); 87 } 88 scanf("%d",&t); 89 while(t--){ 90 scanf("%d%d%d",&cup,&a,&b); 91 ans=Dijkstra(a,b); 92 if(ans!=-1)printf("%d\n",ans); 93 else printf("impossible\n"); 94 } 95 } 96 return 0; 97 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zhsl/archive/2013/01/31/2883859.html

總結(jié)

以上是生活随笔為你收集整理的POJ-3635 Full Tank? 变形最短路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。