[POJ 3635] Full Tank? (多维最短路）
2014-02-13 11:19:09      个评论    来源：[POJ 3635] Full Tank? (多维最短路）

### 解题思路：

```/*
ID: wuqi9395@126.com
LANG: C++
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define PI acos(-1.0)
#define maxn 1010
#define INF 1<<25
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
using namespace std;
int n, m, vis[maxn][105], fuel[maxn], s, e, c;
struct node
{
int x, d, w;
friend bool operator < (node s, node v)
{
return s.w > v.w;
}
};
vector V[maxn];
int bfs()
{
priority_queue q;
mem(vis, 0);
node now, next;
now.x = s, now.d = 0, now.w = 0;
q.push(now);
while(!q.empty())
{
now = q.top();
//        cout<= l && !vis[v][now.d - l])
{
next.x = v, next.d = now.d - l, next.w = now.w;
q.push(next);
}
}
}
return -1;
}
int main ()
{
scanf(%d%d, &n, &m);
for (int i = 0; i < n; i++) scanf(%d, fuel + i);
node tmp;
int u, v;
while(m--)
{
scanf(%d%d%d, &u, &v, &tmp.d);
tmp.x = v, V[u].push_back(tmp);
tmp.x = u, V[v].push_back(tmp);
}
scanf(%d, &m);
while(m--)
{
scanf(%d%d%d, &c, &s, &e);
int ans = bfs();
if (ans == -1) puts(impossible);
else printf(%d
, ans);
}
return 0;
}
```