首页 > 代码库 > poj3159 Candies
poj3159 Candies
题意:
有N个孩子(N<=3000)分糖果。
有M个关系(M<=150,000)。每个关系形如:
A B C
表示第B个学生比第A个学生多分到的糖果数目,不能超过C
求第N个学生最多比第1个学生能多分几个糖果
思路:
dijkstra+heap
实现:
1 #include <iostream> 2 #include <vector> 3 #include <queue> 4 #include <functional> 5 #include <cstdio> 6 using namespace std; 7 8 const int INF = 0x3f3f3f3f; 9 10 struct edge 11 { 12 int to; 13 int cost; 14 }; 15 vector<edge> G[30005]; 16 int d[30005]; 17 typedef pair<int, int>P; 18 19 int Scan() 20 { 21 int res = 0, ch, flag = 0; 22 23 if ((ch = getchar()) == ‘-‘) 24 flag = 1; 25 26 else if (ch >= ‘0‘ && ch <= ‘9‘) 27 res = ch - ‘0‘; 28 while ((ch = getchar()) >= ‘0‘ && ch <= ‘9‘) 29 res = res * 10 + ch - ‘0‘; 30 31 return flag ? -res : res; 32 } 33 34 int main() 35 { 36 int n, m, a, b, l; 37 cin >> n >> m; 38 for (int i = 0; i < m; i++) 39 { 40 a = Scan(); 41 b = Scan(); 42 l = Scan(); 43 edge e; 44 e.to = b; 45 e.cost = l; 46 G[a].push_back(e); 47 } 48 priority_queue<P, vector<P>, greater<P> >myQueue; 49 myQueue.push(P(0, 1)); 50 for (int i = 1; i <= n; i++) 51 { 52 d[i] = INF; 53 } 54 d[1] = 0; 55 while (!myQueue.empty()) 56 { 57 P temp = myQueue.top(); 58 myQueue.pop(); 59 int v = temp.second; 60 if (d[v] < temp.first) 61 continue; 62 for (int i = 0; i < G[v].size(); i++) 63 { 64 edge e = G[v][i]; 65 if (d[e.to] > d[v] + e.cost) 66 { 67 d[e.to] = d[v] + e.cost; 68 myQueue.push(P(d[e.to], e.to)); 69 } 70 } 71 } 72 cout << d[n] << endl; 73 return 0; 74 }
poj3159 Candies
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。