首页 > 代码库 > hdu 4725 The Shortest Path in Nya Graph(建图+优先队列dijstra)
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 0X3f3f3f3fusing 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;}
hdu 4725 The Shortest Path in Nya Graph(建图+优先队列dijstra)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。