POJ-1724 ROADS

POJ-1724 ROADS

题目链接：POJ-1724

题目大意：给定起点终点和路程长度和花费 问你从1到n点在自己钱够的情况下的最短路径

解题思路：最一开始直接暴力的dfs来着 后来是直接就RE了 估计是爆栈了
之后改成用优先队列做，同一起点终点 道路长度从小到大排列 花费也从小到大排 然后用到了重载运算符

代码块：

#include<iostream>
#include<queue>
#include<vector>using namespace std;
typedef struct myNode{int toCity;int roadLen;int cost;// 按路长从小到大 如果路长相同按花费从小到大 bool operator < (const myNode & t)const{if(roadLen == t.roadLen){return cost > t.cost;}return roadLen > t.roadLen;}
} node; 
node temp;
vector<node> vectorA[105];int k, n, r;void bfs();
int main(){cin>>k>>n>>r;for(int i = 0; i < r; i++){int j;cin>>j>>temp.toCity>>temp.roadLen>>temp.cost;vectorA[j].push_back(temp);}bfs();return 0;
}
void bfs(){priority_queue<node> q;temp.roadLen = 0;temp.toCity = 1;temp.cost = 0;q.push(temp);while(!q.empty()){temp = q.top();if(temp.toCity == n){cout<<temp.roadLen;return;}for(int i = 0; i < vectorA[temp.toCity].size(); i++){node n1;n1.toCity = vectorA[temp.toCity][i].toCity;n1.roadLen = vectorA[temp.toCity][i].roadLen + temp.roadLen;n1.cost = vectorA[temp.toCity][i].cost + temp.cost;if(n1.cost <= k){q.push(n1);} }q.pop();}cout<<-1;
}