题目：http://poj.org/problem?id=3635
题意就是给出N个城市，M条边，现在想城市A旅行到城市B，每单位长度的距离花费单位升的汽油。并且各个城市的汽油的价格都不一样。现在要求的是旅行的最小花费是多少。
思路，BFS，用到优先队列，以点，油箱里剩余的油量，以及当前的花费作为状态进行搜索，状态的扩展是对于每一个当前结点来说，有两种扩展方式，一种是加上1升的汽油，价格也增加相应的oil_price[u],另一种就是当前的油量够走到下一个城市时，这时点的信息和油箱的剩余油量需要改变。另外需要注意的就是vis标记，应该在出队列的时候标记，因为这两种方式在扩展的时候有可能扩展到同一个状态就是在同一个城市，并且油箱中剩余油量一样，但此时的价格没办法确定哪个优先，但根据优先队列的在出队列顺序可以知道，这里WA了一次，还有一个WA又是一个很二的错误，边的范围是M * 2，我居然用N * 2;还有一个TLE这题如果用邻接矩阵一个一个去找就是TLE，后来改用伪链表A的。
代码：
#include<cstdio> #include<cstring> #include<queue> using namespace std; #define MAXN 1005 int N, M, cnt; int oil_price[MAXN]; int dist[MAXN][MAXN]; struct Node{ int v, w; int next; }; Node node[MAXN * 20]; int head[MAXN]; struct Point{ int u; int rest_oil; int cost; }; int vis[MAXN][105]; bool operator < (const Point& a, const Point& b) { return a.cost > b.cost; } void add_edge(int u, int v, int c) { node[cnt].v = v; node[cnt].next = head[u]; node[cnt].w = c; head[u] = cnt ++; node[cnt].v = u; node[cnt].next = head[v]; node[cnt].w = c; head[v] = cnt ++; } void BFS(int capacity, int s, int e) { memset(vis, 0, sizeof(vis)); priority_queue<Point>Q; Point start; start.u = s; start.rest_oil = 0; start.cost = 0; Q.push(start); while(!Q.empty()) { Point hd = Q.top(); Q.pop(); int u = hd.u; vis[u][hd.rest_oil] = 1; if(u == e) { printf("%d\n", hd.cost); return; } if(hd.rest_oil < capacity && !vis[u][hd.rest_oil + 1]) { Point t; t.u = u; t.rest_oil = hd.rest_oil + 1; t.cost = hd.cost + oil_price[u]; Q.push(t); } for(int i = head[u]; i != -1; i = node[i].next) { if(hd.rest_oil >= node[i].w && !vis[node[i].v][hd.rest_oil - node[i].w]) { Point t; t.u = node[i].v; t.rest_oil = hd.rest_oil - node[i].w; t.cost = hd.cost; Q.push(t); } } } printf("impossible\n"); } int main() { freopen("poj3635.txt", "r", stdin); int u, v, c; while(scanf("%d%d", &N, &M) != EOF) { cnt = 0; memset(head, -1, sizeof(head)); for(int i = 0; i < N; ++ i) { scanf("%d", &oil_price[i]); } while(M --) { scanf("%d%d%d", &u, &v, &c); add_edge(u, v, c); } int q, capacity, s, e; scanf("%d", &q); while(q --) { scanf("%d%d%d", &capacity, &s, &e); BFS(capacity, s, e); } } return 0; } |