程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [POJ 3635] Full Tank? (多維最短路）

[POJ 3635] Full Tank? (多維最短路）

編輯：C++入門知識

題目大意：

在一個國家有N座城市，有M條道路連接N座城市，每條道路有長度d，一單位長度耗一單位油。在每座城市有加油站，一單位價格為pi。現在有q個詢問，每個詢問代表一輛車從城市st到城市ed的最少花費，其中每輛車的郵箱最大為c。

解題思路：

將每座城市拆分為c個狀態，要麼在這裡加一單位油，要麼從該點走向其他城市。用二維數組表示vis[N][C]該點是否已經訪問過。

/*
ID: [email protected]
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;
}