hdu 4725 The Shortest Path in Nya Graph（建图+优先队列dijstra）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4725

题意：有n个点和n层，m条边，每一层的任意一个点都可以花费固定的值到下一层或者上一层的任意点

然后m条边链接的点可以花费给出的值进行转移，最后问从i点到n点最少要花费多少。

这题点的个数有100000，层数也是100000，不算额外边暴力建边肯定要爆。

所以可以把层数也当成一个点比如说i点在j层于是n+j就与i链接花费0然后i点可以和上下层任意一个点链接

及i与n+j+1链接i与n+j-1链接花费为c，最后额外边就正常处理。

 

#include <iostream> #include <cstring> #include <vector> #include <queue> #include <stdio.h> #define inf 0X3f3f3f3f using namespace std; const int M = 1e5 + 10; int n , m , c , u , v , w , l , pos[M << 1] , dis[M << 1]; struct qnode {int v , w;qnode(int v , int w):v(v) , w(w) {}bool operator <(const qnode &r) const{return w > r.w;} }; struct TnT {int v , w , next;TnT(int v , int w):v(v) , w(w) {} }; vector<TnT> vc[M << 1]; void add(int u , int v , int w) {vc[u].push_back(TnT(v , w)); } bool vis[M << 1]; void dij(int sta) {priority_queue<qnode>q;for(int i = 1 ; i <= 2 * n ; i++) {dis[i] = inf;vis[i] = false;}dis[sta] = 0;q.push(qnode(sta , 0));while(!q.empty()) {int u = q.top().v;q.pop();if(vis[u])continue;vis[u] = true;for(int i = 0 ; i < vc[u].size() ; i++) {TnT gg = vc[u][i];if(dis[gg.v] > dis[u] + gg.w && !vis[gg.v]) {dis[gg.v] = dis[u] + gg.w;q.push(qnode(gg.v , dis[gg.v]));}}} } int main() {int t , ans = 0;scanf("%d" , &t);while(t--) {ans++;scanf("%d%d%d" , &n , &m , &c);for(int i = 1 ; i <= 2 * n ; i++) {vc[i].clear();}for(int i = 1 ; i <= n ; i++) {vis[i] = false;}for(int i = 1 ; i <= n ; i++) {scanf("%d" , &l);pos[i] = l;vis[l] = true;}for(int i = 1 ; i <= n ; i++) {if(pos[i] == 1) {add(pos[i] + n , i , 0);if(n > 1 && vis[pos[i] + 1]) {add(i , pos[i] + 1 + n , c);}}else if(pos[i] == n) {add(pos[i] + n , i , 0);if(n > 1 && vis[pos[i] - 1]) {add(i , pos[i] - 1 + n , c);}}else {add(pos[i] + n , i , 0);if(1 < n && vis[pos[i] + 1]) {add(i , pos[i] + 1 + n , c);}if(n > 1 && vis[pos[i] - 1]) {add(i , pos[i] - 1 + n , c);}}}for(int i = 1 ; i <= m ; i++) {scanf("%d%d%d" , &u , &v , &w);add(u , v , w);add(v , u , w);}dij(1);if(dis[n] == inf)dis[n] = -1;printf("Case #%d: %d\n" , ans , dis[n]);}return 0; }

转载于:https://www.cnblogs.com/TnT2333333/p/6574781.html

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的hdu 4725 The Shortest Path in Nya Graph（建图+优先队列dijstra）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。