ROADS

题目链接：http://poj.org/problem id=1724

题目大意：

有一副有向图，每条边有两个权值，一个是路径长度，一个是走该条路的花销。现在问在不超过K元钱的基础上，从起点到终点的最短路径。

解题思路：

有条件约束的最短路，可以用Dijkstra + heap 做。（采用优先队列）

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #define PI acos(-1.0) #define maxn 1000 #define INF 1<<25 #define mem(a, b) memset(a, b, sizeof(a)) typedef long long ll; using namespace std; struct node { int x, l, t; bool friend operator < (node s, node v) // 先根据路径长度非递减排序，如果长度相同根据费用非递减排序 { if (s.l != v.l) return s.l > v.l; return s.t > v.t; } }; struct E { int d, l, t; }; int k, n, r; vector
               
                 v[110]; int bfs() { node now, tmp; now.x = 1, now.l = 0, now.t = 0; priority_queue
                
                  q; q.push(now); while(!q.empty()) { now = q.top(); q.pop(); if (now.x == n) return now.l; for (int u = 0; u < v[now.x].size(); u++) if (now.t + v[now.x][u].t <= k) { tmp.x = v[now.x][u].d, tmp.l = now.l + v[now.x][u].l, tmp.t = now.t + v[now.x][u].t; q.push(tmp); } } return -1; } int main () { scanf("%d%d%d", &k, &n, &r); while(r--) { int s; E e; scanf("%d%d%d%d", &s, &e.d, &e.l, &e.t); v[s].push_back(e); } printf("%d\n", bfs()); return 0; }

[POJ 1724] ROADS (有约束条件的最短路）

ROADS

题目链接：http://poj.org/problem id=1724

题目大意：

解题思路：