频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
[POJ 3635] Full Tank? (多维最短路)
2014-02-13 11:19:09      个评论    来源:[POJ 3635] Full Tank? (多维最短路)  
收藏   我要投稿

 

题目大意:

在一个国家有N座城市,有M条道路连接N座城市,每条道路有长度d,一单位长度耗一单位油。在每座城市有加油站,一单位价格为pi。 现在有q个询问,每个询问代表一辆车从城市st到城市ed的最少花费,其中每辆车的邮箱最大为c。

解题思路:

将每座城市拆分为c个状态,要么在这里加一单位油,要么从该点走向其他城市。用二维数组表示vis[N][C]该点是否已经访问过。
/*
ID: wuqi9395@126.com
PROG: beads
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;
}


点击复制链接 与好友分享!回本站首页
相关TAG标签 多维
上一篇:C++ I/O 重定向方法(定向到串口或Socket)
下一篇:poj-1699-Best Sequence-dfs+子状态
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站