宁波市建设工程检测协会网站,顺德网站制作案例如何,河北省网站备案系统,菠菜网站搭建怎么做Description 贫穷的小A有一个梦想#xff0c;就是到t国去一次穷游#xff0c;但现实是残酷的。小A所在的世界一共有n(n500)个国家#xff0c;国家与国家之间总共有E(E50000)条道路相连#xff0c;第i个国家对于进入它的外国人都要收取Bi的费用#xff0c;而小A家住…Description 贫穷的小A有一个梦想就是到t国去一次穷游但现实是残酷的。小A所在的世界一共有n(n500)个国家国家与国家之间总共有E(E50000)条道路相连第i个国家对于进入它的外国人都要收取Bi的费用而小A家住在s国他必须通过这些道路在各个国家之间中转最终到达t国除非他运气够好可以直接从s国到达t国。但是贫穷的小A只剩下M(M100)元家底了因此他必须精打细算旅途的费用同时小A对于t国实在太向往了因此他希望能够走最短的路尽快到达t国。这个问题难倒了小A现在他请你帮他算一算他到达t国的最短路径有多长。 Input 第一行输入T(T10)表示有T组数据。每组数据第一行输入n、E、s、t、M分别表示小A所在世界的国家数、国家之间的总道路数、小A的国籍、小A向往的国家以及小A的家底接下来一行输入n个正整数Bi表示第i个国家收取的过路费由于小A是s国人因此s国不会收取但t国会接下来输入E行每行三个正整数u(1un)、v(1vn)、w表示u国和v国之间存在着一条长度为w的无向边可能有重边。输入保证最终结果不会使int溢出。 Output 输出T行正整数第i行表示第i组数据小A花费不超过M元到达t国的最短路。若小A无法到达t国输出-1. Sample Input 3 2 2 1 2 10 20 10 1 2 1 1 2 2 3 1 1 3 10 1 1 1 2 3 1 3 3 1 3 10 1 11 1 1 2 1 1 2 3 2 3 1 Sample Output 1 -1 -1 #include iostream
#include vector
#include queue
#include climits
using namespace std;struct Node {int cost; // 距离int country; // 到达了哪个国家int spent; // 花费了多少钱Node(int c, int co, int s) : cost(c), country(co), spent(s) {}bool operator(const Node other) const {return cost other.cost;}
};typedef pairint, int pii;vectorvectorint dijkstra(vectorvectorpii graph, int start, int max_cost, vectorint countries) {int n graph.size();vectorvectorint dist(n1, vectorint(max_cost 1, INT_MAX));dist[start][0] 0;priority_queueNode, vectorNode, greaterNode pq;pq.push(Node(0, start, 0));while (!pq.empty()) {int cost pq.top().cost;int u pq.top().country;int spent pq.top().spent;pq.pop();if (cost dist[u][spent]) continue;for (auto edge : graph[u]) {int v edge.first;int w edge.second;int new_spent spent countries[v];if (new_spent max_cost cost w dist[v][new_spent]) {dist[v][new_spent] cost w;pq.push(Node(dist[v][new_spent], v, new_spent));}}}return dist;
}int main() {int T;cin T;while (T--) {int n, E, s, t, M;cin n E s t M;vectorint countries(n);for (int i 0; i n; i) {cin countries[i];}vectorvectorpii graph(n);for (int i 0; i E; i) {int u, v, w;cin u v w;graph[u-1].push_back({v-1, w});graph[v-1].push_back({u-1, w});}vectorvectorint dist dijkstra(graph, s-1, M, countries);int min_cost INT_MAX;for (int spent 0; spent M; spent) {min_cost min(min_cost, dist[t-1][spent]);}if (min_cost INT_MAX) {cout -1 endl;} else {cout min_cost endl;}}return 0;
}
