首页 > 代码库 > FZU 2256 迷宫
FZU 2256 迷宫
https://vjudge.net/problem/FZU-2256
题意:略
思路:
在比赛的时候想到了一次dfs,一次bfs但是样例都过不了。。。赛后才知道,距离的更新必须同步,不能先把时光机的距离更新了,再去更新走路的距离。
这题实际上是树上的动态规划,但是可以用一次dfs解决。每次更新的距离的时候,有两个距离需要注意一下,第一个是通过时光机的距离,第二个是实际的距离。时光机的距离如何更新呢,通过上级的距离与(实际的距离加上当前的时光机的距离)进行比较更新。实际的距离的更新就是直接加上当前的实际距离加上走的距离传入下一级就ok了。注意一开始传入的时光机的距离设置为无穷大,因为没有其他时光机可以到达1号房间。
代码:
1 #include <stdio.h> 2 #include <string.h> 3 #include <vector> 4 #include <algorithm> 5 using namespace std; 6 7 struct edge 8 { 9 int from,to,dist; 10 }; 11 12 vector<edge> edges; 13 14 vector<int> v[100005]; 15 16 int d[100005]; 17 int dis[100005]; 18 19 void init(void) 20 { 21 edges.clear(); 22 memset(v,0,sizeof(v)); 23 } 24 25 void adde(int from,int to,int dist) 26 { 27 edge t; 28 t.from = from,t.to = to,t.dist = dist; 29 30 edges.push_back(t); 31 32 int sz = edges.size(); 33 34 v[from].push_back(sz-1); 35 } 36 37 void dfs(int rt,int cst1,int cst2)//cst1是传送,cst2是走路 38 { 39 dis[rt] = min(cst1,cst2); 40 41 for (int i = 0;i < v[rt].size();i++) 42 { 43 int id = v[rt][i]; 44 45 edge t = edges[id]; 46 47 int x = t.to,w = t.dist; 48 49 int cost = min(dis[rt] + d[rt],cst1); 50 51 dfs(x,cost,dis[rt] + w); 52 } 53 } 54 55 int main() 56 { 57 int n; 58 59 while (scanf("%d",&n) != EOF) 60 { 61 init(); 62 63 for (int i = 1;i <= n;i++) 64 { 65 scanf("%d",&d[i]); 66 } 67 68 for (int i = 1;i < n;i++) 69 { 70 int id,dis; 71 72 scanf("%d%d",&id,&dis); 73 74 adde(id,i+1,dis); 75 } 76 77 dfs(1,99999999,0); 78 79 for (int i = 1;i <= n;i++) 80 printf("%d ",dis[i]); 81 82 printf("\n"); 83 } 84 85 return 0; 86 }
FZU 2256 迷宫
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。