[POJ 3635] Full Tank? (多维最短路） - c++编程基础

题目大意：

在一个国家有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; }