题意: n 个人, m 个信息, 每行的信息是 3 个数字, A,B,C, 表示 B 比 A 多出来的糖果不超过 C 个, 问你, n 号人最多比 1 号人多几个糖果
解题关键: 差分约束系统转化为最短路, B-A>=C, 建有向边即可, 与 dijkstra 中的 d[v]>=d[u]+C 相同, 即可求解.
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<cstdlib>
- #include<iostream>
- #include<cmath>
- #include<queue>
- #define max_v 32000
- #define maxm 152000
- #define inf 0x3f3f3f3f
- using namespace std;
- typedef long long ll;
- int head[max_v],tot;
- struct edge{
- int to,w,nxt;
- }e[maxm];
- void add_edge(int u,int v,int w){
- e[tot].w=w;
- e[tot].to=v;
- e[tot].nxt=head[u];
- head[u]=tot++;
- }
- typedef pair<int,int> P;
- int V,n,m,a,b,c,d[max_v];
- void dijkstra(int s){
- priority_queue<P,vector<P>,greater<P>>que;
- fill(d,d+V+1,inf);
- d[s]=0;
- que.push(P(0,s));
- while(que.size()){
- P p=que.top();
- que.pop();
- int v=p.second;
- if(d[v]<p.first) continue;
- for(int i=head[v];i!=-1;i=e[i].nxt){
- edge ex=e[i];
- if(d[ex.to]>d[v]+ex.w){
- d[ex.to]=d[v]+ex.w;
- que.push(P(d[ex.to],ex.to));
- }
- }
- }
- }
- int main(){
- memset(head,-1,sizeof head);
- scanf("%d%d",&n,&m);
- V=n;
- for(int i=0;i<m;i++){
- scanf("%d%d%d",&a,&b,&c);
- add_edge(a,b,c);
- }
- dijkstra(1);
- printf("%d\n",d[n]);
- return 0;
- }
- [poj3159]Candies(差分约束 + 链式前向星 dijkstra 模板)
来源: http://www.bubuko.com/infodetail-2944555.html