題意:給出n個地點 和 每個地點的油價 ,有 m 條邊 , 並給出每條邊長度 。1單位汽油可以走1千米 , 油箱的容量為 c , 在初始點 s 時 , 油箱中的油為 0 , 求s 到 t 的最小花費 。
解法: 定義 狀態 d[i][j] 表示到達 地點 i 且油箱中有 j 單位油時的最小 花費。 對於狀態的轉移時 , 有兩種方法:
1、把每個點的所有狀態都求出
2、不把每個點的狀態都求出 , 而是一單位一單位的加油。
對於第一種方法 , 會超時 , 因為每個點的狀態太多 , 但是能用的狀態就那麼幾個 , 因此得用第二種方法 , 進行狀態的轉移。
確定狀態轉移之後 , 我就可以用 dijkstra + 堆進行優化。
代碼:
#include#include #include #include #include using namespace std; #define maxn 1010 #define INF 0xfffffff struct node { int u , fle , d; bool operator < (const node& chs) const { return d > chs.d; } }; struct edge { int u , d; int next; }grap[20010]; int n , m; int ci[maxn] , pre[maxn][110]; int head[maxn]; int d[maxn][110]; int s , t , c; void init() { memset(head , -1 , sizeof(head)); } void add_edge(int x , int y , int z , int &k) { grap[k].u = y; grap[k].d = z; grap[k].next = head[x]; head[x] = k++; grap[k].u = x; grap[k].d = z; grap[k].next = head[y]; head[y] = k++; } int dijkstra() { priority_queue q; memset(pre , 0 , sizeof(pre)); int i ; memset(d , -1 , sizeof(d)); d[s][0] = 0; node f , e; e.u = s; e.fle = e.d = 0; q.push(e); while(!q.empty()) { e = q.top(); q.pop(); if(e.u == t) return e.d; for(i = head[e.u]; i != -1 ; i = grap[i].next) { if(e.fle >= grap[i].d) { int fuel=e.fle-grap[i].d; if(d[grap[i].u][fuel]==-1||d[grap[i].u][fuel]>e.d) { f.u = grap[i].u; f.fle = fuel; f.d = e.d; d[grap[i].u][fuel] = e.d; // printf("tt.u %d cost %d fuel %d\n",tt.u,tt.fuel,tt.cost); q.push(f); } } if(e.fle < c) { if(d[e.u][e.fle+1]==-1||d[e.u][e.fle+1]>e.d+ci[e.u]) { f.u = e.u; f.fle = e.fle+1; f.d = e.d+ci[e.u]; d[e.u][f.fle] = e.d+ci[e.u]; // printf("tt.u %d cost %d fuel %d\n",tt.u,tt.fuel,tt.cost); q.push(f); } } } } return -1; } int main() { while(scanf("%d %d" , &n , &m) != EOF) { init(); int i , x , y , z; int k = 0; for(i = 0; i < n; i++) scanf("%d" , &ci[i]); for(i = 0; i < m; i++) { scanf("%d %d %d" , &x , &y , &z); add_edge(x , y , z , k); } int p; scanf("%d" , &p); for(i = 1; i <= p; i++) { scanf("%d %d %d" , &c , &s , &t); x = dijkstra(); if(x == -1) cout<<"impossible"<